Print corner nodes of every level in binary tree

Given a binary tree, print corner nodes of every level in it.

 

For example, consider below tree


            1
         /    \
        /      \
       2        3
      /       /   \
     /       /     \
    4       5       6
   /       / \       \
  /       /   \       \
 7       8     9      10

Output:

1
2 3
4 6
7 10

 


 

The idea is very simple. We modify level order traversal of binary tree to maintain level of each node. Then, while doing level order traversal, if the current node happens to be the first node or last node in current level, we simply 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).
 

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 🙂