BST Inorder Predecessor in DSA Javascript

Mental Model

The inorder predecessor of a node in a BST is the node that comes just before it when we list all nodes in order from smallest to largest.

Analogy: Imagine a line of people sorted by height. The inorder predecessor of a person is the person just shorter than them standing immediately before in line.

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑curr

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder predecessor of node with value 5

Goal: Find the node that comes just before 5 in the sorted order of BST nodes

Step 1: Start at node 5, check if left child exists

      5
     / \
    3   7
   / \   \
  2   4   8
 ↑curr

Why: We look left because predecessor is largest node smaller than current

Step 2: Move to left child 3, then go right as far as possible

      5
     / \
    3   7
   / \   \
  2   4   8
       ↑curr

Why: Rightmost node in left subtree is the predecessor

Step 3: Move right from 3 to 4, no further right child

      5
     / \
    3   7
   / \   \
  2   4   8
           ↑curr

Why: 4 is the largest node smaller than 5, so it is the predecessor

Result:

      5
     / \
    3   7
   / \   \
  2   4   8
           ↑curr
Inorder predecessor of 5 is 4

Annotated Code

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function findInorderPredecessor(root, targetVal) {
  // Find the node with targetVal
  let curr = root;
  while (curr !== null && curr.val !== targetVal) {
    if (targetVal < curr.val) {
      curr = curr.left; // move left to find target
    } else {
      curr = curr.right; // move right to find target
    }
  }
  if (curr === null) return null; // target not found

  // If left subtree exists, predecessor is rightmost node there
  if (curr.left !== null) {
    let pred = curr.left;
    while (pred.right !== null) {
      pred = pred.right; // move right to find max in left subtree
    }
    return pred.val;
  }

  // If no left subtree, predecessor is ancestor where current node is in right subtree
  let predecessor = null;
  let ancestor = root;
  while (ancestor !== curr) {
    if (curr.val > ancestor.val) {
      predecessor = ancestor; // potential predecessor
      ancestor = ancestor.right; // move right
    } else {
      ancestor = ancestor.left; // move left
    }
  }
  return predecessor ? predecessor.val : null;
}

// Build example BST
const root = new Node(5);
root.left = new Node(3);
root.right = new Node(7);
root.left.left = new Node(2);
root.left.right = new Node(4);
root.right.right = new Node(8);

const target = 5;
const pred = findInorderPredecessor(root, target);
console.log(`Inorder predecessor of ${target} is ${pred}`);

while (curr !== null && curr.val !== targetVal) {

search for the node with targetVal in BST

if (curr.left !== null) {

if left subtree exists, find rightmost node there

while (pred.right !== null) {

move right to find max node in left subtree

while (ancestor !== curr) {

if no left subtree, find ancestor predecessor

if (curr.val > ancestor.val) {

update predecessor when moving right in ancestor path

Output

Inorder predecessor of 5 is 4

Complexity Analysis

Time: O(h) because we traverse from root to target and possibly down one subtree, where h is tree height

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Compared to inorder traversal of entire tree O(n), this approach is faster as it uses BST properties to find predecessor in O(h)

Edge Cases

Target node has no left subtree and is the smallest node

No predecessor exists, function returns null

DSA Javascript

return predecessor ? predecessor.val : null;

Target node not found in BST

Function returns null indicating no such node

DSA Javascript

if (curr === null) return null;

Target node has left subtree with only one node

That single left child is the predecessor

DSA Javascript

while (pred.right !== null) { pred = pred.right; }

When to Use This Pattern

When asked to find the previous node in sorted order in a BST, reach for the inorder predecessor pattern because it uses BST structure to find it efficiently.

Common Mistakes

Mistake: Trying to find predecessor by full inorder traversal instead of using BST properties
Fix: Use BST rules: predecessor is max node in left subtree or ancestor where current is in right subtree

Mistake: Not handling case when node has no left subtree and predecessor is ancestor
Fix: Add ancestor traversal to find predecessor when left subtree is missing

Summary

Finds the node that comes just before a given node in BST sorted order.

Use when you need the previous smaller value relative to a node in a BST.

The predecessor is the rightmost node in left subtree or the nearest ancestor smaller than the node.