Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
You can just use two vectors to solve this
void printTree (treeNode *root) {
vector<treeNode *> curr_level;
vector<treeNode *> next_level;
curr_level.push_back (root);
while (curr_level.size () != 0) {
for (int i = 0; i < curr_level.size (); i++) {
cout << curr_level[i]->value;
vector<treeNode *> children = curr_level[i]->children;
for (int j = 0; j < children.size (); j++) {
next_level.push_back (children[j]);
}
}
cout << endl;
curr_level = next_level;
}
}
private class TreeNode{
TreeNode left;
TreeNode right;
int data;
}
TreeNode root;
private class NodeLevel{
TreeNode node;
int level;
NodeLevel( TreeNode n, int l ){
node = n;
level = l;
}
}
public void printTheTree(){
LinkedList<NodeLevel> list = new LinkedList<NodeLevel>();
int currLevel = 0;
if( root != null )
list.add( new NodeLevel( root, currLevel ) );
while( !list.isEmpty() ){
NodeLevel nodeLevel = list.remove();
TreeNode node = nodeLevel.node;
if( nodeLevel.level > currLevel ){
System.out.println();
currLevel = nodeLevel.level;
}
System.out.print( node.data );
if( node.left != null )
list.add( new NodeLevel( node.left, currLevel + 1 ) );
if( node.right != null )
list.add( new NodeLevel( node.right, currLevel + 1 ) );
}
}
Recursively traverse the tree. When you recurse, pass a variable indicating the current level + 1. So you'd start with level 0, and when you recurse, you'd pass 1 for the level, when those calls recurse you'd pass 2, etc. Then use that number as an index into an array of sets of nodes and add the node to the set that you get (which corresponds to the index, the node's level). Finally, look at each set one at a time (each set corresponds to a level and has all the nodes from that level) and print everything in the set.
I use a simple queue along with a count.
public static void printLevelByLevelQueue(Node root) {
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (queue.size() > 0) {
int count = queue.size();
while (count > 0) {
count--;
Node temp = queue.remove();
System.out.print(temp.val + " -- ");
if (temp.left != null)
queue.add(temp.left);
if (temp.right != null)
queue.add(temp.right);
}
System.out.println();
}
}
void printTree(TreeNode *root)
{
vector<TreeNode *> curr_level;
vector<TreeNode *> next_level;
curr_level.push_back(root);
while(curr_level.size() != 0)
{
for (int i = 0; i < curr_level.size(); i++ )
{
printf("%d ", curr_level[i]->val);
if (curr_level[i]->left != NULL)
next_level.push_back(curr_level[i]->left);
if (curr_level[i]->right != NULL)
next_level.push_back(curr_level[i]->right);
}
printf("\n");
curr_level = next_level;
next_level.clear();
}
}
calculateheight(TreeNode root){
if(root==null){
return 0;
}else{
return 1+Math.Max(calculateheight(root.left),calculateheight(root.right));
}
}
public static void main(){
int height=caculateheight(root);
for(int level=1;level<=height;level++){
printLevel(root,level);
}
}
printlevel(TreeNode root,int level){
if(root==null){
return;
}
if(level==1){
SOP(root.data)
}
printlevel(root.left,level-1);
printlevel(root.right,level-1);
}
<pre lang="" line="1" title="CodeMonkey78016" class="run-this">#include <cstdlib>
#include <iostream>
#include <conio.h>
#include <queue>
#include <math.h>
using namespace std;
struct Node
{
int data ;
Node *left;
Node *right;
};
queue<Node*> Q;
queue<int> first;
void inorder(Node* root)
{
if(root->left == NULL)
{
cout<<root->data;
}
else
{
inorder(root->left);
cout<< root -> data;
inorder(root->right);
}
}
void BFS()
{
int i(0);
while(!Q.empty())
{
if(Q.size() ==pow(2,i))
{
cout<<endl;
++i;
}
cout<<Q.front()->data;
Q.push(Q.front()->left);
Q.push(Q.front()->right);
Q.pop();
getch();
}
}
int main(int argc, char *argv[])
{
Node *root, *one, *two, *three, *four, *five, *six, ;
root = new Node();
one = new Node();
two = new Node();
three = new Node();
four = new Node();
five = new Node();
six= new Node();
root->data = 0;
one->data = 1;
two->data = 2;
three->data = 3;
four->data =4;
five->data = 5;
six ->data = 6;
root->left = one;
root->right = two;
one->left = three;
one->right = four;
three->left = NULL;
three->right = NULL;
two->left = five;
two->right = six;
four ->left = NULL;
four ->right = NULL;
five ->left = NULL;
five ->right = NULL;
six ->left = NULL;
six ->right = NULL;
Q.push(root);
BFS();
getch();
return(0);
}
</pre><pre title="CodeMonkey78016" input="yes">
</pre>
1. create a dummy node D
- Dr.Sai December 05, 20112. En queue root and D. and go into a loop until Q is not empty.
2. De queue. if De queued node is not D print node and En queue its two children (if they exist). else En queue D and print newline. repeat this step until Q is not empty.
This is called dummy node trick for En queuing and De queuing.
All comparisons to D are pointer comparisons(c/C++) or Object reference comparisons(C# java).