## Printing a Binary Tree in Level Order

September 16, 2010 in binary tree

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; } } } |

Diky Pratansyah said on April 18, 2011

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–

-12Raj said on May 8, 2011

This works for any levels – please verify carefully

0aimless said on May 10, 2011

@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.

+1Anonymous said on May 18, 2011

i 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);

}

}

0Anonymous said on May 18, 2011

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);

}

}

-2Mahmoud Zyoud said on December 13, 2011

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

-1fresher said on June 15, 2011

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

0aimless said on June 15, 2011

@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.

0Himanshu said on June 21, 2011

What 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.

0moonus said on September 9, 2011

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

0nihi said on September 14, 2011

Another 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

0moonus said on September 14, 2011

I 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.

0Abhishek said on December 19, 2011

void 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;

}

}

}

0Abhishek said on December 19, 2011

0HT said on February 13, 2012

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

+2Venki said on April 11, 2012

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

0siva said on April 13, 2012

I 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

0Lei said on July 4, 2012

I 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);

}

0SR said on August 13, 2012

Why 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.

+1她比烟花寂寞 said on September 22, 2012

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

0Jeo Smith said on November 17, 2012

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

0Ren Yi said on January 31, 2013

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.

+2sandhyalal said on May 16, 2013

very nice sol..

0Laiq Ahmed said on June 22, 2013

Following 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

0Laiq Ahmed said on June 24, 2013

The 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

0ashish said on August 26, 2013

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

0Gautam said on October 9, 2013

nodesQueue.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;

0AAKASH ANUJ said on March 19, 2014

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.

0Developer-Looking for job said on April 19, 2014

Simple C# BFS code is as follows:

0