Question: Given a node and head of a binary tree, find it's InOrder Successor. Please note that tree structure doesn't have a parent pointer.
Answer:
what we have to do is take a separate variable that will represent running parent. Initialize the variable to some already agreed value say infinity.
Now search for the number (node given)
The trick is that whenever you go left in searching of that node, make the value of the variable as the value of the parent (I mean from where you go left).
If u go right, keep it as it is...
Once you are done searching for that node, check whether the node has right child:
- If it has a right child, you know how to find inorder successor (most left node from right child).
- If node does not have a right child, this number (parent) is your answer. If this variable has infinity, it means that no inorder successor exists.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.
Hi YuanYun,
Thanks for passing by this post.
I received your comment on this post in my mail box. If you are still not clear about we can have a discussion on it.
Regards,
Akash
Hi, Akash
Thanks very much for your reply. I misunderstood your solution at that time, after re-read your post carefully, I understood it and recognized that your solution is perfect.
There are few corner cases with this approach. For example consider an arbitrary tree, and if we input a node which will be last node of inorder traversal, the current method will return incorrect answer. There will be no successor to the last element of inorder traversal.