Print Right View of a Binary Tree

Given a binary tree, write an efficient algorithm to print right view of given binary tree.

 

For example, the right view of given binary tree is 1, 3, 6, 8

 
Print Right View of a Binary Tree.

 
 

1. Iterative Implementation using Queue –

 

In iterative version, we perform level order traversal of the tree. We can modify level order traversal to maintain nodes in current level. Then if current node is last node of current level, we print it.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

 

2. Recursive implementation using Hashing –

 

We can also solve this problem by using Hashing. The idea is to traverse the tree in preorder fashion and pass level information in function arguments. For every node encountered, we insert the node and level information into the map. Finally when all nodes are processed, we traverse the map and print the right view.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
 

 

Recursive implementation (using Preorder traversal) –

 

We can also solve this problem by using constant space and in linear time. The idea is to traverse the tree in reverse preorder fashion (visit right subtree before left subtree) and maintain maximum level visited so far. If current level is more than maximum level visited so far, then the current node is the last node of current level and we print it and also update last level to current level.

 
C++ implementation –
 

Download   Run Complete Code

 
The time complexity of above solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.

 
Exercise: Print Left View of a Binary Tree

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz