Wednesday, March 11, 2015

Left view of a binary tree

Given a binary tree, how do we print the left view of it?

For example, consider the simple binary tree below

   1
 / \
2   3


The left view of this is 1, 2. Similarly consider one more example

            1
          /  \
         2    3
             / \
            4   5

Left view for this tree contains 1, 2, 4.

If the tree is completely left skewed or right skewed, the left view contains all the nodes like the following. For example

1                1
 \              /
  2            2
   \          /
    3        3


The left view for both of the above trees is 1, 2, 3.

We can solve this problem in two ways, one iterative and the other using recursion.

Recursive method:
In this approach to the traversal function, we send two additional parameters along with root node, one is the current level and another is maximum level. maximum level is a reference parameter which remembers it's value between the function calls. 
We compare the current and maximum level values, if the max level is less than current level we print the data at root node and update the maximum level. Recursively call the same function for the left and right sub-trees by incrementing the current level.

Iterative method:

We use the level order traversal method to print the first node in each level. While storing the nodes in the queue, we store a separator (NULL) node to distinguish between the levels.

Here is the C++ code which implements the above approaches.Both run in O(n) time complexity.