# Tree: Level Order Traversal

# Tree: Level Order Traversal

vimal_Parthan + 9 comments **My Java Solution**Queue queue=new LinkedList();

queue.add(root);

while(!queue.isEmpty())

{

Node tempNode=queue.poll();

System.out.print(tempNode.data+" ");

if(tempNode.left!=null)

queue.add(tempNode.left);

if(tempNode.right!=null)

queue.add(tempNode.right);

}ameykulkarni + 0 comments [deleted]h4ck3rviv3k + 3 comments You need to type cast "queue.poll()" because it will give you an object so you need to type cast it to Node object "(Node)queue.poll()".

inno_irving_est1 + 2 comments omg i was getting frustrated with this one. Its weird it works if I instantiate the queue as a linked list, but it doesnt work with PriorityQueue. Shouldnt PriorityQueue work also? I almost had the same solution as vimal_Parthan but I had it initialized Queue queue = PriorityQueue() but this didnt work

anirudh_pratap22 + 1 comment or you can define the Queue using generics

miere00 + 1 comment @aniruth_prata22 was right. I don't understand why someone have down voted his answer....

void levelOrder(Node root) { Queue<Node> queue=new LinkedList<>(); queue.add(root); while(!queue.isEmpty()) { Node tempNode=queue.poll(); System.out.print(tempNode.data+" "); if(tempNode.left!=null) queue.add(tempNode.left); if(tempNode.right!=null) queue.add(tempNode.right); } }

atulDc + 0 comments [deleted]

mvbelgaonkar + 0 comments [deleted]

Vsahith + 0 comments queue.poll() returns an object. you have to do

`Queue<Node> queue = new LinkedList();`

or do this :

`Node tempNode = (Node)queue.poll();`

enmar + 1 comment Just a note for anyone reading, you should never use raw types; always use generics. The ability to use raw types only exists to support legacy Java code.

Queue<Node> q = new LinkedList<Node>();

is the proper way of instantiating your LinkedList in this case.

From

*Effective Java*, 2nd ed.

**Given that you shouldn't use raw types, why did the language designers allow them? To provide compatibility.**The Java platform was about to enter its second decade when generics were introduced, and there was an enormous amount of Java code in existence that did not use generics. It was deemed critical that all this code remains legal and interoperable with new code that does use generics. It had to be legal to pass instances of parameterized types to methods that were designed for use with ordinary types, and vice versa. This requirement, known as migration compatibility, drove the decision to support raw types.

jscupc + 0 comments Hi @enmar, all,

I've been working in some HackerRank exercices in which a queue implementation was required, so I implemented it myself using an array and a couple of indexes (head and tail). However, I see that in many answers people refer to to the List/Queue/Map/Set classes defined in java.util.* Can we also use them to solve the exercices? I thought that we were required to implement all these things manually in the exercices (specially for selection process exams). Could you please clarify it?

Best wishes,

jscupc

eshmatov + 1 comment Not a good design, you could do it more elegant!

orionsongs + 2 comments Not a good comment! You could provide constructive feedback or a better example, instead of just a negative opinion.

eshmatov + 1 comment Sometimes this is fine too, a person should be able to think for better results, instead just asking any random ideas comes to mind.

pranaytanniru111 + 0 comments Your negative opinion had many negative likes 😉

g_snehasish + 0 comments Share your solution if you have one First ,then criticize

abhinavgolum97 + 7 comments Can anyone tell me what is the problem here ?

C solution :

void levelOrder(node * root) { static int i=0; if(i==0){ printf("%d ",root->data); i++; } if(root==NULL) return; if(root->left==NULL && root->right==NULL); return; if(root->left!=NULL) printf("%d ",root->left->data); if(root->right!=NULL) printf("%d ",root->right->data); levelOrder(root->left); levelOrder(root->right); }

Thanks!

wallah + 1 comment i think u did i just like first question in trees . if u test it on copy on simple example u will find it

abhinavgolum97 + 2 comments what is wrong here ? I got right answer when i traced it using an example.

wallah + 0 comments look it did it without recursion . and when i traced on my example i get error

meraz_zatin + 0 comments That you are thinking actually happens to the left subtree first and then goes further left. so the first line of traversal is fine. However when it traverses down it goes left first. what you actually are thinking is hapening in left subtree and then the same thing occurs int he lower trees.

i_mohamed + 0 comments your code will work this way

_____5_____ _2_""""""""_7_ _1"""_3_""_6_""_8_ 0"2""3 4""5"8""7"9

for this tree your answer will be

5 2 7 1 3 0 2 3 4 6 8 5 8 7 9 which is wrong

akscool100 + 0 comments the operation here on right patr of the tree is happening only after the operation getting finished on the left part. thats why you are getting error as it should happen at once.

shaif_ansari22 + 0 comments you are traversing the left subtree then right subtree and because of that the order is not coming properly.

kasa_pranay9 + 0 comments Absolutely ur program is wrong because ur program is first printing the left subtree node values then its coming to right but u need to print left and right which are in same level

surajkumar_cse + 0 comments It will traverse through all branches of left first then it will come to right.

jeet_txt + 0 comments Through the lines where you use recursion i.e levelOrder(root->left) and levelOrder(root->right) you are first traversing the left side of the binary tree and then the right. Thus your usage of recursion here is wrong.

hammeramr + 1 comment Solution with generics

void levelOrder(Node root) { Queue<Node> Q = new LinkedList<Node>(); Q.add(root); while(!Q.isEmpty()) { Node n = Q.poll(); System.out.print(n.data + " "); if(n.left != null) Q.add(n.left); if(n.right != null) Q.add(n.right); } }

jscupc + 0 comments Hi @hammeramr,

I've been working in some HackerRank exercices in which a queue implementation was required, so I implemented it myself using an array and a couple of indexes (head and tail). However, I see that in many answers people refer to to the List/Queue/Map/Set classes defined in java.util.* Can we also use them to solve the exercices? I thought that we were required to implement all these things manually in the exercices (specially for selection process exams). Could you please clarify it?

Best wishes,

jscupc

reasonet + 1 comment **Python solution:**import sys def levelOrder(root): if root is None: return q = [root] while(len(q) > 0): sys.stdout.write(str(q[0].data) + ' ') n = q.pop(0) if not n.left is None: q.append(n.left) if not n.right is None: q.append(n.right)

sayanarijit + 2 comments **Great...**Little modified version:def levelOrder(root): if root is None: return q = [root] while(len(q) > 0): n = q.pop(0) print n.data, if n.left: q.append(n.left) if n.right: q.append(n.right)

AffineStructure + 0 comments def levelOrder(root): deck = deque() if not root: return None else: deck.append(root) while deck: x = deck.popleft() print x.data, if x.left: deck.append(x.left) if x.right: deck.append(x.right)

farhadkeramatim + 2 comments Little more modification (shortest version I could do):

def levelOrder(root): q = [root] while q: n = q.pop(0) print n.data, if n.left: q.append(n.left) if n.right: q.append(n.right)

jamalelkassimi + 0 comments Very nice way of using the pop function to traverse the tree in a level-order fashion.

eloyekunle + 1 comment This is actually less efficient since pop(0) is an O(n) operation in python. Removing from the front of a list (as opposed to the end) is highly inefficient. The other solution above using

`deque`

is actually better than this since deques are optimized for constant time pops and appends from both ends.jeet_txt + 1 comment well I tried to learn more about it and it says that pop operation on any arbitrary value is O(n) while if it is performed on the last element it is O(1). So is the time complexity for the pop operation different when performed on the first element of the queue ? . I am confused... do let me know what you think ?

eloyekunle + 0 comments Yes it is different. The full meaning of

`deque`

is*Double-Ended Queues*. Stacks/Queues, normally are optimized for constant time insertions/deletions on one end only. According to Python's documentation:Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

b160028 + 0 comments why you are using Queue type reference variable since also it is perfectly working with linkedlist type i.e.

LinkedList l=new LinkedList();

what is the problem with the above way...

priyeshu + 15 comments Here's simplest C++ solution I could write

`#include<queue> void LevelOrder(node * root) { queue<node*> q; node *temp = root; while(temp!=NULL) { cout<<temp->data<<" "; if(temp->left!=NULL) q.push(temp->left); if(temp->right!=NULL) q.push(temp->right); temp = q.front(); q.pop(); }`

anvitakamat + 0 comments [deleted]anvitakamat + 0 comments [deleted]anvitakamat + 0 comments [deleted]anvitakamat + 0 comments [deleted]anvitakamat + 1 comment # include<queue> void LevelOrder(node * root) { queue<node *> q; node *temp=root; if(root != NULL) { q.push(root); } while(!q.empty()) { cout<<temp->data<<" "; if(temp->left != NULL) { q.push(temp->left); } if(temp->right != NULL) { q.push(temp->right); } q.pop(); temp= q.front(); } }

pavitra_ag + 1 comment can you explain what is the difference in your code and @priyeshu's code. his code gives abort called error in 2 test cases.Why? Thanks in advance.

hardikrana437 + 0 comments check for 1 element in tree.

Scent_Leader + 1 comment Wow I really need to work more Object-like... My solution works but is not be optimal... I like yours.

void LevelOrder(node * root){ static int depth = 1; static int level = 1; static bool next = false; if(level == depth){ cout << root->data << " "; } if((root->left || root->right || next) && level == depth) next = true; else next = false; ++depth; if(root->left && depth <= level) LevelOrder(root->left); if(root->right && depth <= level) LevelOrder(root->right); --depth; if(next && depth == 1){ ++level; next = false; LevelOrder(root); } }

anonyms + 1 comment dude how did u come up with this... now bfs using single stack can also be done using similar logic

Scent_Leader + 0 comments Dunno. Just wanted a recursive solution...

rk3102882_ak + 1 comment can anyone explain last two code of the program i didn't get it.

Scent_Leader + 0 comments I think I can explain. First the

*push()*function**insert always at the end**of an array. Second the*pop()*function**delete the first element**in an array.For the program of anvitakamat:

// Basically he creates an array queue<node *> q; // q = [] // ...then a pointer to the root tree node *temp = root; //insert the root value into the array q.push(root); // q = [root] // We arrive to the while loop and q is not empty while(!q.empty()){ // ... now we are in ... }

Now is the tricky part...

cout<<temp->data<<" "; // it print the root's data value since temp points to root if(temp->left != NULL) // if left branch available q.push(temp->left); // ... it stacks left branch // q = [root, root->left] if(temp->right != NULL) // if right branch available q.push(temp->right); // ... it stacks right branch // q = [root, root->left, root->right] q.pop(); // q = [root->left, root->right] temp= q.front(); // temp points now to root->left // and it starts over again // and it will stacks all left and right sides but print one data at a time

Hope it's been helpful. If you have more questions go on.

kashish25798 + 1 comment Here's my code for level order but its showing some error i couldnt find plz help

int rear=0,front=-1;

struct queue { node* value; }s[50];

int isFull() { if(rear==50) return 1; else return 0; }

int isEmpty() { if(front==-1) return 1; else return 0; }

void push(node * root) { if(!isFull()) {queue[rear].value=root; rear++;} }

node* pop() { node* temp; if(!isEmpty()) { temp=queue[front].value; front++;} return temp; }

void LevelOrder(node * root) { node* temp=root; while(temp) { printf("%d",temp->data); if(temp->left) push(temp->left); if(temp->right) push(temp->right); temp=pop(); }

Scent_Leader + 0 comments First your answer is in C not C++ which is different. By looking at your code I guess you're a beginner so I suggest you to read this : C Programming (second edition) by Brian and Dennis

And for pointers exclusively : Better understand of advanced pointers (C)

As for the solution I mimick the C++ solution of

**this**comment section.**Side Note:**This is my solution in**C**and this is not the complete code to run it but only the interesting part.*(I highly recommend to be able to deal with pointers)*#include<stdio.h> // Library for basic functions #include<stdlib.h> // String functions and memory allocations function // The presuming structure used in this exercise typedef struct node { char *data; struct node *left; struct node *right; } node; // Example of memory allocation function node *getNodeSpace(void){ node *s = NULL; if((s = (node *) malloc(sizeof(node))) == NULL) exit(1); return s; } // The function in C void LevelOrder(node *root){ int i = 0; // allow to go through the storing array int x = 0; // count the number of node node *temp; // node holder node **base; // pointer to storing array node **s; // storing array if(root != NULL){ *s = root; base = s; ++x; } while((temp = *(base+i)) != NULL && x){ printf("%s\n", temp->data); if(temp->left) if(*++s = getNodeSpace()){ (*s)->data = temp->left->data; (*s)->left = temp->left->left; (*s)->right = temp->left->right; ++x; } if(temp->right) if(*++s = getNodeSpace()){ (*s)->data = temp->right->data; (*s)->left = temp->right->left; (*s)->right = temp->right->right; ++x; } ++i; --x; } }

See ya!

zjuPeco + 0 comments I tried your code but met "Aborted called" in some test samples. Anyone knows why?

himanhsu54 + 1 comment gives "abort called " on two test cases. but when i run a similar solution (pasted below ) from @anvitakamat it runs sucessfully.

# include<queue> void LevelOrder(node * root) { queue<node *> q; node *temp=root; if(root != NULL) { q.push(root); } while(!q.empty()) { cout<<temp->data<<" "; if(temp->left != NULL) { q.push(temp->left); } if(temp->right != NULL) { q.push(temp->right); } q.pop(); temp= q.front(); } }

can you figure out what is going wrong.?

prashu08 + 0 comments while(!q.empty()) { temp= q.front(); q.pop(); cout<<temp->data<<" "; if(temp->left != NULL) { q.push(temp->left); } if(temp->right != NULL) { q.push(temp->right); } }

rishabhkumarjha + 0 comments Does not run for all test cases. Abort call.

akshaybapat04 + 0 comments I wrote a similar code.. Both of our solutions fail testcases 3 and 5..

pavitra_ag + 0 comments your solution gives abort called error

tanmay777 + 0 comments Beauty Man!

juneja_amit25 + 0 comments is it neccessary to store the root value into the temp variable?

sm_khan2010 + 3 comments Without using any other data structure

public void LevelOrder(Node root){ int i = 0; int h = height(root); for(i=1; i<=h; i++){ printTreeLevelRec(root, i); } } int height(Node n){ if(n==null) return 0; if(n.left==null && n.right==null) return 1; int lheight = height(n.left); int rheight = height(n.right); return Math.max(lheight, rheight) + 1; } void printTreeLevelRec(Node node, int desired){ if(node==null) return; if (desired == 1) System.out.print(node.data+ " "); printTreeLevelRec(node.left, desired-1); printTreeLevelRec(node.right, desired-1); }

The_Speck + 0 comments This is great. Thanks for the post. Gave me great insight about this problem without using any other data structure. Thanks.

19soumikrakshi96 + 0 comments This is exactly how the problem is given in GeeksForGeeks. But how do I count the number of nodes in each level using this algo???

Rehmanali + 0 comments Dont we need to keep while(desired>0) in printTreeLevelRec method?

anishhota + 0 comments **PYTHON SOLUTION:**def levelOrder(root): queue = [] queue.append(root) while(len(queue)>0): node = queue.pop(0) print node.data, if node.left: queue.append(node.left) if node.right: queue.append(node.right)

jonmcclung + 3 comments This was a fun problem where I got to make use of the linked lists we learned in the last chapter (:

`#include <list> void LevelOrder(node * root) { list<node*> nodes; if (root) { nodes.push_back(root); } for (list<node*>::iterator it = nodes.begin(); it != nodes.end(); it++) { printf("%d ", (*it)->data); if ((*it)->left) { nodes.push_back((*it)->left); } if ((*it)->right) { nodes.push_back((*it)->right); } } }`

IntidSammers + 0 comments [deleted]tomlankhorst + 1 comment I tried just the same but with vectors instead of lists. Why would I get a segmentation fault like i do?

`void LevelOrder(node * root) { std::vector<node*> N; if( root ) { N.push_back( root ); for( std::vector<node*>::iterator i = N.begin(); i != N.end(); i++ ) { std::cout << (*i)->data << " "; if( (*i)->left ) N.push_back( (*i)->left ); if( (*i)->right ) N.push_back( (*i)->right ); } } }`

dgodfrey + 1 comment Because unlike linked list (std::list), vector iterators become invalidated when you insert. So i++ is causing a segmentation fault. You need to do this:

`for (...; /* delete i++ */) { if ((*i)->left || (*i)->right) { if ((*i)->left) N.push_back(...) if ((*i)->right) N.push_back(...) } else { i++; } }`

tomlankhorst + 2 comments Is that because of the relocation of data when the original allocated size does not suffice?

dgodfrey + 0 comments Yes (sorry or the long reply).

isanrivkin + 0 comments Thanks for that man !

HuangZhenyang + 1 comment I don't quit understand why should use

nodes.push_back(root);

dgodfrey + 1 comment The first node we need to visit is the root, then it will be its children (inside the loop).

HuangZhenyang + 1 comment Er,sorry,I just cann't know why use list....... And about the loop,does the loop will get the same level node?

dgodfrey + 0 comments Using

`list`

is optional. The fact is that we need a First-In First-Out (FIFO) data structure. This is what a`queue`

is normally used for. tomlankhorst figured out a way to emulate FIFO with a linked list.The loop will first start with the

`root`

node that was added before it started. It will print the root node and then add the left node and the right node and do the same thing starting with the left node. Then the left node's children will be added.

pverardi + 0 comments Java Solution. Simple Breadth First Solution. The key is to remember to use a Queue and the rest will fall in line.

void LevelOrder(Node root) { if (root == null) return;

`Queue<Node> q = new LinkedList<>(); q.add(root); while (!q.isEmpty()){ Node temp = q.poll(); System.out.print(temp.data + " "); if (temp.left != null) q.offer(temp.left); if (temp.right != null) q.offer(temp.right); } }`

return_void + 1 comment Simple with a queue

#include <queue> void LevelOrder(node * root) { queue<node*> nodes; if (root) nodes.push(root); for (; !nodes.empty(); nodes.pop()) { cout<<nodes.front()->data<<' '; if (nodes.front()->left) nodes.push(nodes.front()->left); if (nodes.front()->right) nodes.push(nodes.front()->right); } }

pfeiferbit + 0 comments [deleted]

runcy + 2 comments When can we see support for python? It's already part of the 30-Days-Code tutorial (in day 23) with python support

adiman423 + 0 comments Same here. I would like to be able to do this challenge in Python, but if C++ is my only choice then I will do it in C++.

micahwood50 + 0 comments Two months and still no support fot Python...

CodeMunkey + 0 comments If you're familiar with Breadth-First Search, the solution is quite simple. I'm not sure why the editorial states that this is recursive, when it is in fact iterative.

ThecoolKid + 2 comments `void LevelOrder(Node root) { java.util.LinkedList<Node> q = new java.util.LinkedList<Node>(); if(root!=null) q.add(root); while(q.peekFirst() != null ){ Node current = q.poll(); System.out.print(current.data + " "); if(current.left!=null) q.add(current.left); if(current.right!=null) q.add(current.right); }`

etayluz + 3 comments C solution:

`void LevelOrder(node * root) { node * nodeList[10000]; int n = 1; int i = 0; nodeList[0] = root; while (i < n) { node *thisNode = nodeList[i]; if (thisNode->left) { nodeList[n++] = thisNode->left; } if (thisNode->right) { nodeList[n++] = thisNode->right; } i++; } for (int i = 0; i < n; i++) { node *thisNode = nodeList[i]; printf("%d ", thisNode->data); } }`

prendergast + 0 comments Better use a dynamic data structure like a "linked list" or "queue" to avoid the hardcoded size of an array.

positivedeist_07 + 0 comments Can u pls explain ur solution? It appears to be so elegant and clean

positivedeist_07 + 0 comments Hey!! I just walked through ur solution and man, was that brilliant! :) so very thoughtful of you. I have a couple of doubts, though.

Isn't "*thisnode" will be created everytime the loop runs? Wouldn't that have a slightly more effect on space complexity? Also, The while loop runs even though there are no nodes left in the tree (i.e., when both the if conditions return false). It runs few times just to prove the while condition false (so that i becomes equal to n). Is that really necessary? Can't we stop as soon as both the if conditions fails with another "else if" of "if" statement?

I'd be really grateful if u helped me out. Thankyou.

GauravRatnawat + 0 comments thanks dude

Sort 249 Discussions, By:

Please Login in order to post a comment