Find next node in same level for given node in a binary tree

Given a binary tree and a node in it, write an efficient algorithm to find its next node in same level as given node.

 

For example, consider below binary tree


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

Next node of 2 is 3
Next node of 5 is 6
Next node of 7 is 8
Next node of 8 is null


 

Simple solution would be to perform level order traversal of the tree. We can modify level order traversal to maintain level number of each node. Then if the given node is found, we return its immediate right node which is present at the same level.

 
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).
 


 

We can also solve this problem by using constant auxiliary space and in linear time. The idea is to traverse the tree in preorder fashion and search for the given node. Once the given node is found, we mark its level number. Then, the first node encountered at same level is the next right node.

 
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