Friday, May 1, 2015

Level order traversal of the binary tree from the bottom

Given a binary tree, how do we print the nodes in level order starting from the bottom.

For example for the following tree, the output should be 2 3 1

    1
  /  \
 2    3

An obvious solution is to first find the maximum levels of the tree. we can print the nodes from maximum level to minimum level. This is not so efficient, because to print each level we need to traverse all the nodes.

Another solution is that we can modify the level order traversal. We need an additional stack to store the nodes. Instead of printing the values of the nodes as soon as they are deleted from the queue, we can add them to stack. Later, we can pop the elements from the stack and print them. This will print the elements in reverse level order.

Here is the C++ code for the second approach.