Friday, March 13, 2015

Right view of the binary tree

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

For example, consider the simple binary tree below

   1
 / \
2   3


The right view of this is 1, 3. Similarly consider one more example

            1
          /  \
         2    5
        / \  
       3   4 

Right view for this tree contains 1, 5, 4.

This is similar to my last post which asks for the left view of the binary tree. We just need to make the following changes to the algorithms discussed in the earlier post.

In case of iterative solution, we need to add the right child first to the queue before adding the left child.

In the recursive approach, we need to first recurse on the right child. Below is the modified code.