Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Find the in-order successor of a given node in a binary search tree


Note:

We can do in-order traversal, which will give us a sorted array and then find the in-order successor very easily.

  • But the time complexity of in-order traversal in O(n).

Where as finding the in-order successor is very frequently used operation. Hence, we need to find better solution.

  • We will show the solution which will run in O(log(n)).

We will assume the BST is constructed in a way that each node has a reference to its parent.

Case I : Node has a right subtree

In that case we need to find the left most node in its right subtree which is also the min (lowest) node in its right subtree.

InOrder-Successor-Case-1

Case II : Node does not have a right subtree

InOrder-Successor-Case-2

Pseudo code

inorderSuccessor (node n) {

  if (n has a right subtree) {
    return leftmost child of right subtree;
  } else {
    while (n is a right child of n.parent) {
      n = n.parent; // Climb up 
    }
    return n.parent; // Deepest ancestor in the path from root, for which the node would be in the left sub-tree
  }
}

Watch the following excellent video to understand this algorithm in more detail!

Solution

If we have a BST in which each node has a reference to its parent node then the following solution can give us the inOrderSuccessor of the given node.


  • CTCI_6_4.6

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *