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.