Find inorder successor of a given key in a BST.

Given a binary search tree (BST) and a key we have to find its inorder successor.

In BST, inorder successor of the given key is the next element in the in-order traversal of it. If the key is last node in the BST then there is no successor so return null.

Example

Input:
       5
      /  \
     /    \
    2     12
   / \    / \
  /   \  /   \
 1    3 9    21


Key = 5,
key = 12,
key = 21    
         
Output:
successor of 5 = 9
successor of 12 = 21
successor of 21 = null        

After this we will see how to find the inorder predecessor of a given key in BST which will be similar to this.

The left most child in the right-subtree of the given key is the in-order successor of the key because an element’s in-order successor is the node with minimum value in its right subtree. If there is no such element tree, then the successor can be found in one of its ancestor.

To find the ancestor we can keep moving toward the root until we come across an element which is the left most child of its parent. If there exits no such element then there is no in-order successor present.

Recursive solution: Inorder successor of given key in BST.

Conceptually this is how it works.

• The above conditions can be checked recursively using a function.
• Search the given key in the tree and update the successor to the current node before moving to the left sub tree.
• If node is found in the tree, then we return the minimum value from the right subtree.
• And if the right subtree does not exists then the successor is one of the ancestors which has been already updated while search for the given key.

We will use a helper function to find the minimum value in the right subtree.

//find the minimum value node in a BST
const findMinimum = (root) => {
  while(root.left !== null){
    root = root.left;
  }
  
  return root.val;
}

const findSuccessor = (root, succ, key) => {
  //base case
  if(root === null){
    return null;
  }
  
  // if the node with given key is found, 
  // then its successor will be the node with least value in its right subtree
  if (root.val === key) {
    if (root.right != null) {
      return findMinimum(root.right);
    }
  }

  // if the node is greater than the key, recur for left subtree
  else if (key < root.val) {
    // update successor to current node
    succ = root;
    return findSuccessor(root.left, succ, key);
  }

  // if the node is less than key, recur for right subtree
  else {
    return findSuccessor(root.right, succ, key);
  }

  return succ ? succ.val : null;
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(5);  
tree.left = new Node(2);  
tree.right = new Node(12);  
tree.left.left = new Node(1);  
tree.left.right = new Node(3);  
tree.right.left = new Node(9);  
tree.right.right = new Node(21);

console.log(findSuccessor(tree, null, 5));

Output:
       5
      /  \
     /    \
    2     12
   / \    / \
  /   \  /   \
 1    3 9    21 

9

---

Iterative solution

The above idea can be converted to iterative solution without any hustle. All we have to do is use the while loop and keep on iterating by updating the successor properly.

Helper function

This helper returns the node, rather than the value which we had done for the recursive solution.

//find the minimum value node in a BST
const findMinimum = (root) => {
  while(root.left !== null){
    root = root.left;
  }
  
  return root;
}

const findSuccessorIterative = (root, key) => {
  let node = null;

  while (true) {
      // if the node is greater than key, go to left subtree
      if (key < root.val) {
        // update successor to current node
        succ = root;
        root = root.left;
      }

      // if the node is less than the key, go to right subtree
      else if (key > root.val){
        root = root.right;
      }

      // if node has same value as the key, 
      // then its successor is minimum value node in its right subtree
      else {
        if (root.right != null) {
          succ = findMinimum(root.right);
        }
        break;
      }

      // key doesn't exist in binary tree
      if (root == null){
        return null;
      }
    }

    // return Successor
    return succ ? succ.val : null;
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(5);  
tree.left = new Node(2);  
tree.right = new Node(12);  
tree.left.left = new Node(1);  
tree.left.right = new Node(3);  
tree.right.left = new Node(9);  
tree.right.right = new Node(21);

console.log(findSuccessorIterative(tree, 5));

Output:
       5
      /  \
     /    \
    2     12
   / \    / \
  /   \  /   \
 1    3 9    21 

9

The time complexity for both the solution is O(n) and space complexity is O(n) (if call stack is considered for recursive solution) otherwise O(1) (for iterative solution).