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

Binary Tree Level-Order Traversal Using Depth First Search (DFS) | LeetCode
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.

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.

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.

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;

  }

}

 DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.

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

http://massivealgorithms.blogspot.com/2014/06/leetcode-binary-tree-level-order.html
Read full article from Binary Tree Level-Order Traversal Using Depth First Search (DFS) | LeetCode