Printing a Binary Tree in Level Order

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.6/5 (94 votes cast)
Printing a Binary Tree in Level Order, 4.6 out of 5 based on 94 ratings

48 thoughts on “Printing a Binary Tree in Level Order

  1. Diky Pratansyah

    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]
    -33
  2. Anonymous

    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]
    -1
  3. Anonymous

    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]
    -4
    1. aimless

      @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]
      +6
  4. Himanshu

    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]
    +1
  5. nihi

    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]
    +1
    1. moonus

      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]
      +1
  6. Abhishek

    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]
    +1
  7. Abhishek

    VA:F [1.9.22_1171]
    +2
  8. HT

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

    VA:F [1.9.22_1171]
    +4
  9. Profile photo of sivasiva

    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
  10. Profile photo of LeiLei

    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
  11. SR

    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
  12. Pingback: Level Order Binary Tree Traversal | This is how Cheng grows up

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

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

  15. Profile photo of Ren YiRen Yi

    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
  16. Profile photo of Laiq AhmedLaiq Ahmed

    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
  17. Gautam

    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]
    +1
  18. Pingback: Serialization/Deserialization of a Binary Tree | Parabolic Evidence

  19. Pingback: %leetcode% Populating Next Right Pointers in Each Node | 橡皮塞MM

  20. AAKASH ANUJ

    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
  21. Profile photo of Developer-Looking for jobDeveloper-Looking for job

    Simple C# BFS code is as follows:

    VN:F [1.9.22_1171]
    0
  22. Pingback: Algorithms |

  23. Profile photo of qilu xieqilu xie

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

    VN:F [1.9.22_1171]
    0
  24. Profile photo of qilu xieqilu xie

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

    VN:F [1.9.22_1171]
    0
  25. PJ

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

    VA:F [1.9.22_1171]
    0
  26. Pingback: Printing a Binary Tree in Level Order | moonstonelin

  27. Fang

    2
    / \
    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;

    }

    VA:F [1.9.22_1171]
    0
  28. Pingback: MultiLevel Pie Chart Using D3 | know your javascript

  29. Pingback: Multi Level Pie Chart Using D3 | experience@imaginea

  30. Yusen Zhang

    this chunk of code on the original post is wrong. You can’t push NULL to the list. Please change it so that people won’t get confused.

    VA:F [1.9.22_1171]
    0
  31. 北斗衛星時計を採用し、中国が自主開発した北斗衛星ナビゲーションシステムの2世代の時報信号を時報、北斗衛星に覆われた範囲内で、すべての時計分秒違わない、時間精度で制御コンマ

    北斗衛星時計を採用し、中国が自主開発した北斗衛星ナビゲーションシステムの2世代の時報信号を時報、北斗衛星に覆われた範囲内で、すべての時計分秒違わない、時間精度で制御コンマ1秒以内に。北斗衛星時計は「1、2、3を測るかも」など何項のハイテク機能、即ち、衛星信号時刻合わせ、校正時計時間;二定、すなわち指向、位置決め、出力経緯度、高度の座標、地図区枚コード;三測、すなわち、高さを測る、温度を測る測気圧。BOTTEGA VENETA財布コピー未来の北斗衛星の時計を持ってショートメッセージ通信機能を使用することができ、この機能はユーザーの緊急援助、ときに、野外旅行者やアウトドア者に危険が警察に助けを求めに限り、腕時計のSOSキーをすることで、自分の位置情報や救難信号衛星で、事前設定の端末に送信して。世界の四大衛星ナビゲーションシステムは、中国の北斗衛星ナビゲーションシステムを備えているこの機能。 http://www.ooowatch.com/tokei/hermes

    VA:F [1.9.22_1171]
    0
  32. Houman

    Queues do not have push and pop operations. You’re thinking of a stack. Other than that, this was reasonably helpfull.

    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.