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    7

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

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.

VN:F [1.9.22_1171]
Rating: 4.7/5 (45 votes cast)
Printing a Binary Tree in Level Order, 4.7 out of 5 based on 45 ratings

31 responses to Printing a Binary Tree in Level Order

  1. 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–

    VA:F [1.9.22_1171]
    -14
    • Raj said on May 8, 2011

      This works for any levels – please verify carefully

      VA:F [1.9.22_1171]
      0
  2. @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.

    VA:F [1.9.22_1171]
    +1
  3. 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);
    }
    }

    VA:F [1.9.22_1171]
    0
  4. 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);
    }
    }

    VA:F [1.9.22_1171]
    -2
  5. In the first algorithm.. I believe we need to empty the nextLevel queue after swap?

    VA:F [1.9.22_1171]
    0
    • @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.

      VA:F [1.9.22_1171]
      0
  6. 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.

    VA:F [1.9.22_1171]
    0
    • The NULL is ok to push because of the line “if(currNode)” to avoid the unexpected behavior.

      VA:F [1.9.22_1171]
      0
  7. 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

    VA:F [1.9.22_1171]
    0
    • 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.

      VA:F [1.9.22_1171]
      0
  8. 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;

    }
    }
    }

    VA:F [1.9.22_1171]
    0
  9. VA:F [1.9.22_1171]
    0
  10. for the second solution, you may also use a dummy node to achieve the same idea.

    VA:F [1.9.22_1171]
    +2
  11. The question is about just the level order traversal, why do we need two queues?

    VN:F [1.9.22_1171]
    0
  12. 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

    VN:F [1.9.22_1171]
    0
  13. 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);
    }

    VN:F [1.9.22_1171]
    0
  14. 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.

    VA:F [1.9.22_1171]
    +2
  15. Much thanks for the excellent articles you’ve posted. One question about that post, why should we push the NULL node to the queue?

    VN:F [1.9.22_1171]
    -1
    • Of course you don’t need to. But you have put null check before you push the pointer to the queue.

      VN:F [1.9.22_1171]
      -1
  16. 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.

    VN:F [1.9.22_1171]
    +2
  17. very nice sol..

    VA:F [1.9.22_1171]
    0
  18. 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

    VN:F [1.9.22_1171]
    0
  19. can anyone please tell me why the first solution uses two queues. Can’t we just use one queue.

    VA:F [1.9.22_1171]
    0
  20. 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;

    VA:F [1.9.22_1171]
    0
  21. 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.

    VA:F [1.9.22_1171]
    0
  22. Simple C# BFS code is as follows:

    VN:F [1.9.22_1171]
    0
  23. Hey just wanted to give you a quick heads up and let you know a few of the pictures aren’t loading correctly.

    I’m not sure why but I think its a linking issue. I’ve tried it in two
    different web browsers and both show the same results.

    VA:F [1.9.22_1171]
    0
  24. Lal said on July 2, 2014

    Create 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-

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.