Print left view of binary tree

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

 

For example, the left view of given binary tree is 1, 2, 4, 7

 

print left view of binary tree
 


 

1. Iterative implementation –

 

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 first 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. If the level is visited for the first time, then we insert the current node and level information into the map. Finally when all nodes are processed, we traverse the map and print the left 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(nlog(n)).
 


 

3. 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 preorder fashion and maintain maximum level visited so far. If current level is more than maximum level visited so far, then the current node is the first 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.

 
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