Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]

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. We have already seen how to do level order traversal here.

Example
So consider the tree:
      1
   /    \
  2      3
 /   \   /    \
4   5  6   7
The BFS or level order traversal here is :
1 2 3 4 5 6 7

Last time we used BFS, but this time it is not allowed.

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 or Depth of a Binary Tree.

void printLevel(BinaryTree *p, int level) {
  if (!p) return;
  if (level == 1) {
    cout << p->data << " ";
  } else {
    printLevel(p->left, level-1);
    printLevel(p->right, level-1);
  }
}
 
void printLevelOrder(BinaryTree *root) {
  int height = maxHeight(root);
  for (int level = 1; level <= height; level++) {
    printLevel(root, level);
    cout << endl;
  }
}

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

Thanks.