Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level.

3 / \ 9 20 / \ 15 7For example, the level order output of the tree above is:

`3 9 20 15 7`

By now, you should be able to do pre-order, in-order, and post-order tree traversal off the top of your head. These are called Depth First Search (DFS), since they visit the tree by proceeding deeper and deeper until it reaches the leaf nodes.

DFS uses a data structure called Stack and is commonly implemented using recursion (since function calls are pushed and popped off the memory stack). If recursion is not allowed, we can simulate the recursion by using iterative method with the help of stack. See my older post: Binary Search Tree In-Order Traversal Iterative Solution on how to do a DFS iteratively using a stack.

The most natural solution for level-order traversal is Breadth First Search (BFS), since it visits the nodes level by level. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure. If you are curious, level-order traversal can be implemented using DFS too. See my next post: Binary Tree Level-Order Traversal Using Depth First Search (DFS) for the challenge.

In order to print the binary tree in level order with newline in the end of each level, we can utilize two queues. The first queue stores the current level’s nodes, while the second queue stores the next level’s nodes (the current level nodes’ children).

When the first queue is emptied, we know that it must have reached the end of the current level, therefore we print a newline. Then, we switch the emptied first queue with the second queue (which is populated with the next level’s nodes). Then we repeat the process over again.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
void printLevelOrder(BinaryTree *root) { if (!root) return; queue<BinaryTree*> currentLevel, nextLevel; currentLevel.push(root); while (!currentLevel.empty()) { BinaryTree *currNode = currentLevel.front(); currentLevel.pop(); if (currNode) { cout << currNode->data << " "; nextLevel.push(currNode->left); nextLevel.push(currNode->right); } if (currentLevel.empty()) { cout << endl; swap(currentLevel, nextLevel); } } } |

Is it possible that a solution exists using only one single queue? Yes, you bet. The single queue solution requires two extra counting variables which keep tracks of the number of nodes in the current level (** nodesInCurrentLevel**) and the next level (

**). When we pop a node off the queue, we decrement**

*nodesInNextLevel***by**

*nodesInCurrentLevel**one*. When we push its child nodes to the queue, we increment

**by**

*nodesInNextLevel**two*. When

**reaches**

*nodesInCurrentLevel**0*, we know that the current level has ended, therefore we print an endline here.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
void printLevelOrder(BinaryTree *root) { if (!root) return; queue<BinaryTree*> nodesQueue; int nodesInCurrentLevel = 1; int nodesInNextLevel = 0; nodesQueue.push(root); while (!nodesQueue.empty()) { BinaryTree *currNode = nodesQueue.front(); nodesQueue.pop(); nodesInCurrentLevel--; if (currNode) { cout << currNode->data << " "; nodesQueue.push(currNode->left); nodesQueue.push(currNode->right); nodesInNextLevel += 2; } if (nodesInCurrentLevel == 0) { cout << endl; nodesInCurrentLevel = nodesInNextLevel; nodesInNextLevel = 0; } } } |

It works if tree just has 3 level. But it won’t work if tree has more than 3 level

I’m searching for algorithm that can work in a tree that has more than 3 level. It would be nice if you can help me find the algorithm ’cause i have given up

–Thanks–

-26This works for any levels – please verify carefully

0@Diky:

Here is solution using two queue:

http://ideone.com/4Nso9

Here is solution using single queue:

http://ideone.com/xgtHY

watch closely, they are not much different.

+2i think it can b done recursively without using queue..i have the following code..please correct me if I am worng…

void printlevelorder(node *root)

{

int h = height(root);//get the height of the tree.I the example given above height of the tree is 2

int i ;

for(i=0;idata);

else

{

printnodes(root->left,level-1);

printnodes(root->right,level-1);

}

}

-2void printlevelorder(node *root)

{

int h = height(root);//get the height of the tree.I the example given above height of the tree is 2

int i ;

for(i=0;idata);

else

{

printnodes(root->left,level-1);

printnodes(root->right,level-1);

}

}

-5heey.. how ur code will run…can u trace the code if u could<?

-2In the first algorithm.. I believe we need to empty the nextLevel queue after swap?

+1@fresher: SWAP swaps the contents so after this operation, contents of currentLevel goes to nextLevel queue (which makes it empty) and content of nextLevel goes to currentLevel queue.

+2What if one of the node is null?

nodesQueue.push(currNode->left);

nodesQueue.push(currNode->right);

this will give the unexpected behavior.

We can chek for the null and then do the increment.

0The NULL is ok to push because of the line “if(currNode)” to avoid the unexpected behavior.

0Another variation of this question is print it from bottom to top.

15 7

9 20

3

How about Spiral printing (left->right, then right->left, then left->right)

3

20 9

15 7

0I guess this is already been in another topic, if you could take a look at zig-zag in order level by level. And even print the silhouette of a binary tree. Explore more, you will find a lot of interesting topics.

0void printLevelOrderSpiral(node* root) {

if (!root) return;

deque nodesQueue;

int nodesInCurrentLevel = 1;

int nodesInNextLevel = 0;

nodesQueue.push_back(root);

bool dir = true;

while (!nodesQueue.empty()) {

node* currNode ;

if(dir){

currNode = nodesQueue.front();

nodesQueue.pop_front();

}

else {

currNode = nodesQueue.back();

nodesQueue.pop_back();

}

nodesInCurrentLevel–;

if (currNode) {

cout <data <left);

nodesQueue.push_back(currNode->right);

}

else {

nodesQueue.push_front(currNode->right);

nodesQueue.push_front(currNode->left);

}

nodesInNextLevel += 2;

}

if (nodesInCurrentLevel == 0) {

cout << endl;

nodesInCurrentLevel = nodesInNextLevel;

nodesInNextLevel = 0;

dir = dir ? false: true;

}

}

}

0+1for the second solution, you may also use a dummy node to achieve the same idea.

+4The question is about just the level order traversal, why do we need two queues?

-1I have doubt regarding 2nd solution.

(1) why you are using front() and pop() methods, you can use directly pop() method?

(2) with out checking left child and right child existed or not you are pushing into queue

0I have a question here:

When we push the left child and right child to the queue, should we check whether they are null or not? If null, we should not push it to the queue.

if (currNode) {

cout <data <left)

nextLevel.push(currNode->left);

if(!currNode->right)

nextLevel.push(currNode->right);

}

0Why not add a special node in the queue representing a new line. Start with root followed by new line node in the queue. Every time a newline node is encountered print a new line and put the newline node back into the queue. End when no nodes are printed between two removal of the newline node from the queue.

+2Much thanks for the excellent articles you’ve posted. One question about that post, why should we push the NULL node to the queue?

0Of course you don’t need to. But you have put null check before you push the pointer to the queue.

0Pingback: Level Order Binary Tree Traversal | This is how Cheng grows up

Pingback: Amazon interview preparation | What I learn, I blog !

Pingback: Idea Board Printing a Binary Tree in Level Order | Idea Board

Another way with one queue could be to have a NewLine node in the queue at the very beginning. Whenever you pop the NewLine node out, you print a blank line and push it at the end of the queue again. So that you don’t have to mess up with the code of counting.

+2very nice sol..

0Following are my efforts for solving the level-order problem using two queues. I think using single queue or two queues doesn’t matter since for two queue solution at every iteration the maximum number of nodes present in one of the two queues is O(n/2). and the algorithm can be executed in O(n).

I found following solution by leetCoder using depth first traversal as well. The solution is interesting and give deeper picture of traversals and their uses, but I think the mathematics for calculating complexity is not correct… the algorithm’s complexity is O(nlgn) not O(n).

following is the link

http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal/51

0The solution posted by leetcoder using Depth first traversal indeed takes O(n) time NOT nlogn. I misunderstood the complexity.

Following is the link

http://discuss.leetcode.com/questions/49/binary-tree-level-order-traversal/51

0can anyone please tell me why the first solution uses two queues. Can’t we just use one queue.

0nodesQueue.push(currNode->left);

nodesQueue.push(currNode->right);

nodesInNextLevel += 2;

The above code is true only when tree have both children,

I believe the best things should be as follows

if(currNode->left)

nodesQueue.push(currNode->left);

nodesInNextLevel += 1;

if(currNode->right)

nodesQueue.push(currNode->right);

nodesInNextLevel += 1;

+1Pingback: Serialization/Deserialization of a Binary Tree | Parabolic Evidence

Pingback: %leetcode% Populating Next Right Pointers in Each Node | æ©¡çš®å¡žMM

Here is the code in C++. It is always better to check if a node is NULL before enqueueing it. If the left or the right child of a node is NULL, we do not enqueue it in the queue.

0Simple C# BFS code is as follows:

0Create an empty queue

The root of the tree is added in the queue.

The queue is removed and printed. If the removed item has any child(ren), add it/them in the queue.

Repeat the last step until the queue is empty.

For explanation and code http://www.algoqueue.com/algoqueue/default/view/8519680/print-binary-tree-by-level-i-

0Pingback: Algorithms |

c# version of the first solution (using two queues)

0C# version of the second solution (only using one queue)

0Why will you hard code the value += 2 every time? Why are you even pushing NULL (left tree there right NULL or vice versa)?

0Very nicely done! thanks

0Pingback: Printing a Binary Tree in Level Order | moonstonelin

Java implementation of the one queue solution:

https://gist.github.com/dmnugent80/3276172fdf0de44d637f

02

/ \

4 7

/ \ \

6 3 9

/ \ \

1 5 8

list[0] = 2

list[1] = 4,7

list[2] = 6,3,9

list[3] = 1,5,8

public class Node {

Node left;

Node right;

int value;

}

List<ArrayList> createLevelList(TreeNode root) {

if (root == null) return null;

List<ArrayList> results = new ArrayList<ArrayList>();

List curList = new ArrayList();

List nextList = new ArrayList();

while (curList.size() > 0) (

for (int i=0; i<curList.size(); i++) {

Node curNode = curList.get(i);

if (curNode.right != null) nextList.add(curNode.right);

if (curNode.left != null) nextList.add(curNode.left);

if (i == curList.size()-1) {

results.add(curList);

curList = nextList;

nextList = new ArrayList();

}

}//end for i

}

return results;

}

0