Find inorder predecessor of a given key in a BST.

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

In BST, an inorder predecessor of the given key is the previous greater element in the in-order traversal of it. If the key is first node in the BST then there is no predecessor so return null.

Example

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


Key = 21,
key = 3,
key = 1    
         
Output:
predecessor of 21 = 12
predecessor of 3 = 2
predecessor of 1 = null    

We have already seen how to find the inorder successor of a given key in BST. Using the same approach we are going to find the predecessor.

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

To find the ancestor which is predecessor we can keep moving up towards root until we come across an element which is the right most child of its parent. If there exits no such element then there is no inorder predecessor present.

Recursive solution: Inorder predecessor 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 predecessor to the current node before moving to the right sub tree.
• If node is found in the tree, then we return the key with the greatest value from the left subtree.
• And if the left subtree does not exists then the predecessor is one of the ancestors which has been already updated while searching for the given key.

We will be using an helper function to find the node with max value in the tree.

const findMaximum = (root) => {
  while(root.right){
    root = root.right;
  }
  
  return root.val;
}

const findPredecessorRecursive = (root, pred, key) => {
  //base case
  if(root === null){
    return null;
  }
  
  // if node has same value as the key, 
  // then its predecessor is greatest value node in its left subtree
  if (root.val === key) {
    if (root.left !== null) {
      return findMaximum(root.left);
    }
  }

  // if node is greater than the key, recur for left subtree
  else if (key < root.val) {
    return findPredecessorRecursive(root.left, pred, key);
  }

  // if node is less than the key, recur for right subtree
  else {
    // update predecessor to current node
    pred = root;
    return findPredecessorRecursive(root.right, pred, key);
  }

  return pred ? pred.val : null;
}

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(findPredecessorRecursive(tree, null, 9));

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

5

---

Iterative solution: Predecessor in BST.

We can easily convert the above recursive solution to an iterative one, with some minor changes.

Helper function

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

const findMaximum = (root) => {
  while(root.right){
    root = root.right;
  }
  
  return root;
}

const findPredecessorIterative = (root, key) => {
    let pred = null;

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

      // if node value is less than key, go to right subtree
      else if (key > root.val) {
        // update predecessor to current node
        pred = root;
        root = root.right;
      }

      // if node has same value as the key, 
      // then its predecessor is greatest value node in its left subtree
      else {
        if (root.left!= null) {
          pred = findMaximum(root.left);
        }
        break;
      }

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

    // return predecessor if any
    return pred ? pred.val : null;
}

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(findPredecessorIterative(tree, null, 9));

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

5

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