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

1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

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