Binary Tree Level-Order Traversal Using Depth First Search (DFS)

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. Breadth First Search (BFS) is not allowed.

     3
   /  \
  9   20    
     /  \
    15    7

For example, the level order output of the tree above is:

3 
9 20 
15 7

In my last post: Printing Binary Tree in Level Order, we discuss how to print a tree using Breadth First Search (BFS). The challenge now is, can you do it using Depth First Search (DFS) this time?

Hint:
Write a function call printLevel(BinaryTree *p, int level) which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing printLevel.

Solution:
printLevel function can be solved using DFS. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height of a Binary Tree.

Further Thoughts:
If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.

Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?

Answer:
Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in O(N) time, where N is the number of nodes in the binary tree and we assume that the binary tree is balanced.

We first compute the complexity of printLevel for the kth level:

T(k) = 2T(k-1) + c
     = 2k-1 T(1) + c
     = 2k-1 + c

Assuming it’s a balanced binary tree, then it would have a total of lg N levels.

Therefore, the complexity of printing all levels is:

T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 22 + ... + 2lg N-1 + c
= O(N)

Finding the maximum height of the tree also takes O(N) time, therefore the overall complexity is still O(N).

VN:F [1.9.22_1171]
Rating: 4.5/5 (33 votes cast)
Binary Tree Level-Order Traversal Using Depth First Search (DFS), 4.5 out of 5 based on 33 ratings

24 thoughts on “Binary Tree Level-Order Traversal Using Depth First Search (DFS)

  1. aimless

    @Elite(1337c0d3r)
    I tried calculating the Big O and I think it should be NlogN, please follow this link
    http://ideone.com/EjbXP

    also when the tree is absolutely skewed, height shall be N, in that case it will be square(N)
    N appears way too optimistic.

    VA:F [1.9.22_1171]
    +6
  2. 老杨

    I think you don’t have to calculate the height. You can use the return value from printLevel, if you find at a specific level it’s all empty, return 0, and break the loop. Code could be like this:

    int printLevel(BinaryTree *p, int level) {
    __if (!p) return 0;
    __if (level == 1) {
    ___cout <data <left, level-1);
    ___int rcright = printLevel(p->right, level-1);
    ___return rcleft || rcright;
    }
    }

    VA:F [1.9.22_1171]
    +2
  3. 老杨

    … sorry I messed up the format, this one should be ok

    int printLevel(BinaryTree *p, int level) {
    __if (!p) return 0;
    __if (level == 1) {
    ____cout <data <left, level-1);
    ____int rcright = printLevel(p->right, level-1);
    ____return rcleft || rcright;
    __}
    }

    VA:F [1.9.22_1171]
    +1
  4. mukesh

    If the binary tree is not full then the code will not work.To avoid this first check that the left or right node of the tree is null.If it is null then don’t call printLevel function.
    there is a slightly modification in the printLevel function

    void printLevel(BinaryTree *p, int level) {
    if (!p) return;
    if (level == 1) {
    cout <data <left!=NULL) //to check whether the left is NULL
    printLevel(p->left, level-1);
    if(p->right!=NULL) //to check whether the right is NULL
    printLevel(p->right, level-1);
    }
    }

    VA:F [1.9.22_1171]
    0
  5. mukesh

    sorry….there is some problem in the editor.It doen’t print as it was typed.
    In the else part of printLevel function add two if statements to check whether the p->left and p->right is NULL.if it is not null then only call printLevel function
    ………
    if(p->left!=NULL)
    printLevel(p->left,level-1);
    if(p->right!=NULL)
    printLevel(p->right,level-1);
    ………..

    VA:F [1.9.22_1171]
    -1
  6. Prateek Caire

    Complexity should be nlogN
    First iteration, nodes visited: 1
    2nd : 1 + 2^1
    3: 1+2^1+2^2
    .
    .
    .
    logn: 1+2^1+2^2 + …+2^(logn-1)
    1+2^1+2^2 + …+2^(logn-1) = O(n)
    Adding all : nLogn

    VA:F [1.9.22_1171]
    0
  7. «мιиð_ωαяяιoя»

    Binary Tree Level-
    Order Traversal Using
    “Depth First Search
    (DFS)”..?
    How you say it’s DFS..?

    VA:F [1.9.22_1171]
    0
  8. Pingback: Binary Tree Traversal – Speculation437

  9. Pete Li

    Generally speaking, time complexity analysis should use worse-case. What is the worst case here? Skewed tree. What is the time complexity of level order traverse this skewed tree? O(n^2)
    So the answer should be O(n^2)

    VA:F [1.9.22_1171]
    +5
    1. jure

      Even by intuition, since we are repeating the DFS process for printing each level( we always starts from the root and finished at the leaf, however we only print out the nodes in the exact level), we are repeating visiting N nodes for all lgN levels, so the expected complexity is O(NlgN). The worst case happens when it’s a skew tree, where O(N^2) complexity takes place.

      VN:F [1.9.22_1171]
      +2
    2. Jack Master

      Consider this for the balanced case.
      To traverse a balanced tree of height h (h = log n), we traverse 2^h – 1 nodes.

      Then, for a tree of size n and height h (balanced):
      2^0 + 2^1 + …. + 2^(h-1) + 2^h
      This is a geometric series. Sum from 2^0 to 2^(m-1) for arbitrary reasonable m is 2^m – 1, thus, we have 2^h – 1 + 2^h = O(2^h) = O(n)

      VA:F [1.9.22_1171]
      0
      1. theOtherWC

        Notice that each time ROOT is passed to printLevel, which is essentially a Preorder. This is O(nlogn). To make it O(n), return immediately when level<1.

        VA:F [1.9.22_1171]
        0
  10. Hardy

    Also want to contribute my iterative solution:

    VN:F [1.9.22_1171]
    -1
  11. Vlad

    Just wanted to not that it’s not necessary to determine the tree height in advance. Please see my solution:

    VA:F [1.9.22_1171]
    -1

Leave a Reply

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

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

*