BST Inorder Predecessor in DSA Typescript

Mental Model

The inorder predecessor of a node in a BST is the node with the next smaller value when we list all nodes in order.

Analogy: Imagine a sorted list of books on a shelf. The inorder predecessor of a book is the book immediately to its left on the shelf.

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

Dry Run Walkthrough

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

Goal: Find the node with the largest value smaller than 4 in the BST

Step 1: Start at root (5), compare 4 with 5

5 [curr] -> 3 -> 7 -> 2 -> 4 -> 8

Why: We need to find node 4, so we compare with root first

Step 2: 4 < 5, move to left child (3)

3 [curr] -> 2 -> 4 -> 8

Why: Since 4 is less than 5, predecessor must be in left subtree or ancestor

Step 3: 4 > 3, record 3 as potential predecessor, move to right child (4)

4 [curr]

Why: 4 is greater than 3, so 3 could be predecessor, check right subtree

Step 4: Found node 4 (4 <= 4), check if it has left subtree by moving left

4 [curr], move left (null)

Why: If left subtree exists, predecessor is max in left subtree

Step 5: Node 4 has no left child, so predecessor is last recorded node 3

Predecessor = 3

Why: No left subtree means predecessor is ancestor recorded earlier

Result:

Predecessor = 3

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function bstInorderPredecessor(root: TreeNode | null, targetVal: number): TreeNode | null {
  let predecessor: TreeNode | null = null;
  let curr = root;

  // Find the target node while tracking potential predecessor
  while (curr !== null) {
    if (targetVal <= curr.val) {
      curr = curr.left; // move left if targetVal is smaller or equal
    } else {
      predecessor = curr; // record current as potential predecessor
      curr = curr.right; // move right to find closer predecessor
    }
  }

  // If no predecessor found, return null
  if (predecessor === null) return null;

  return predecessor;
}

// Build BST for example
const root = new TreeNode(5,
  new TreeNode(3,
    new TreeNode(2),
    new TreeNode(4)
  ),
  new TreeNode(7,
    null,
    new TreeNode(8)
  )
);

const targetVal = 4;
const pred = bstInorderPredecessor(root, targetVal);
if (pred !== null) {
  console.log(`Predecessor = ${pred.val}`);
} else {
  console.log("Predecessor = null");
}

while (curr !== null) {

Traverse tree to find target and track predecessor

if (targetVal <= curr.val) { curr = curr.left; }

Move left if target is smaller or equal, no update to predecessor

else { predecessor = curr; curr = curr.right; }

Update predecessor and move right if target is greater

if (predecessor === null) return null;

Return null if no predecessor found

Output

Predecessor = 3

Complexity Analysis

Time: O(h) because we traverse from root down to target node where h is tree height

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

vs Alternative: Naive approach would do full inorder traversal O(n), this method is faster by using BST properties

Edge Cases

Target node is the smallest node in BST

No predecessor exists, function returns null

DSA Typescript

if (predecessor === null) return null;

Target node has a left subtree

Predecessor is the maximum node in left subtree, found naturally during traversal

DSA Typescript

if (targetVal <= curr.val) { curr = curr.left; } updates predecessor in left subtree

Target node not present in BST

Function returns predecessor of where target would be inserted (largest < targetVal)

DSA Typescript

while (curr !== null) { ... }

When to Use This Pattern

When asked for the previous smaller node in BST order, use inorder predecessor logic by tracking ancestors and left subtree max.

Common Mistakes

Mistake: Not updating predecessor when moving right in the tree
Fix: Always update predecessor to current node before moving right if targetVal > curr.val

Mistake: Confusing inorder predecessor with inorder successor
Fix: Remember predecessor is next smaller, successor is next larger

Mistake: Trying to explicitly find the target node first then check left subtree
Fix: The single traversal handles both ancestor and left subtree cases automatically

Summary

Finds the node with the next smaller value than the target in a BST.

Use when you need the immediate smaller neighbor of a node in sorted BST order.

Track ancestors smaller than target during search; traversal handles left subtree implicitly.