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 (nodesInNextLevel). When we pop a node off the queue, we decrement nodesInCurrentLevel by one. When we push its child nodes to the queue, we increment nodesInNextLevel by two. When nodesInCurrentLevel reaches 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–
Raj said on May 8, 2011
This works for any levels – please verify carefully
aimless 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.
Anonymous 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);
}
}
Anonymous 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);
}
}
Mahmoud Zyoud said on December 13, 2011
heey.. how ur code will run…can u trace the code if u could<?
fresher said on June 15, 2011
In the first algorithm.. I believe we need to empty the nextLevel queue after swap?
aimless 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.
Himanshu 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.
moonus said on September 9, 2011
The NULL is ok to push because of the line “if(currNode)” to avoid the unexpected behavior.
nihi 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
moonus 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.
Abhishek 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;
}
}
}
Abhishek said on December 19, 2011
HT said on February 13, 2012
for the second solution, you may also use a dummy node to achieve the same idea.
Venki said on April 11, 2012
The question is about just the level order traversal, why do we need two queues?
siva 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
Lei 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);
}
SR 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.
她比烟花寂寞 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?
Jeo 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.
Ren 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.
sandhyalal said on May 16, 2013
very nice sol..