Set next pointer to inorder successor of all nodes in binary tree

Given a binary tree where each node has one extra pointer next, set next pointer to inorder successor for all nodes in the binary tree.

 

For example, consider below tree. Here, blue dotted line represents next pointer for each node.

 
Set next pointer to inorder Successor


Inorder Successor of node 4 is 2
Inorder Successor of node 2 is 1
Inorder Successor of node 1 is 7
Inorder Successor of node 7 is 5
Inorder Successor of node 5 is 8
Inorder Successor of node 8 is 3
Inorder Successor of node 3 is 6
Inorder Successor of node 6 is null

 

 
The idea is to perform in-order traversal of the tree and maintain previously processed node for every tree node. Then, for every node in in-order traversal, we set its next node to previously visited node. This is demonstrated below in C++ –

 

Download   Run Complete Code

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

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
someone
Guest

please do it in JAVA
and also put all the programs in python.