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.

Practice

1. What is the inorder predecessor of a node in a Binary Search Tree (BST)?

easy

A. The right child of the given node

B. The node with the largest value smaller than the given node

C. The left child of the given node

D. The node with the smallest value larger than the given node

Solution

1. Step 1: Understand inorder traversal in BST

   Inorder traversal visits nodes in ascending order of their values.

2. Step 2: Define inorder predecessor

   The inorder predecessor of a node is the node visited just before it in inorder traversal, which means it has the largest value smaller than the given node.

3. Final Answer:

   The node with the largest value smaller than the given node -> Option B

4. Quick Check:

   Inorder predecessor = largest smaller value [OK]

Hint: Predecessor is just before in sorted order [OK]

Common Mistakes:

• Confusing predecessor with successor
• Thinking predecessor is always left child
• Assuming predecessor is the parent node

2. Which TypeScript function signature correctly represents a method to find the inorder predecessor of a BST node?

easy

A. function findInorderPredecessor(root: TreeNode): void

B. function findInorderPredecessor(node: TreeNode): number

C. function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null

D. function findInorderPredecessor(): boolean

Solution

1. Step 1: Identify required inputs and outputs

   To find the inorder predecessor, we need the BST root and the target node, and we return the predecessor node or null if none.

2. Step 2: Match function signature

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null matches this: it takes root and node, returns TreeNode or null.

3. Final Answer:

   function findInorderPredecessor(root: TreeNode, node: TreeNode): TreeNode | null -> Option C

4. Quick Check:

   Correct inputs and output type [OK]

Hint: Function needs root, node, returns node or null [OK]

Common Mistakes:

• Missing root parameter
• Returning wrong type like number or boolean
• No parameters or void return type

3. Given the BST below and the node with value 15, what is the inorder predecessor?

       20
      /  \
    10    30
      \
      15

medium

A. 10

B. 15

C. 20

D. 30

Solution

1. Step 1: Perform inorder traversal around node 15

   Inorder traversal visits nodes in order: 10, 15, 20, 30.

2. Step 2: Find node before 15 in traversal

   The node before 15 is 10, so 10 is the inorder predecessor.

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Predecessor of 15 = 10 [OK]

Hint: Predecessor is previous in sorted order [OK]

Common Mistakes:

• Choosing the node itself as predecessor
• Choosing parent node incorrectly
• Confusing predecessor with successor

4. Consider this TypeScript code snippet to find the inorder predecessor of a node in a BST:

function inorderPredecessor(root: TreeNode | null, node: TreeNode): TreeNode | null {
  let predecessor: TreeNode | null = null;
  while (root) {
    if (node.val <= root.val) {
      root = root.left;
    } else {
      predecessor = root;
      root = root.right;
    }
  }
  return predecessor;
}

What is the bug in this code?

medium

A. It does not handle the case when node has a left subtree

B. It incorrectly updates predecessor when node.val > root.val

C. It returns the successor instead of predecessor

D. It causes infinite loop when root is null

Solution

1. Step 1: Understand inorder predecessor logic

   If node has a left subtree, predecessor is the rightmost node in that subtree, which this code does not check.

2. Step 2: Analyze code behavior

   The code only moves down from root to find predecessor by comparing values, missing the left subtree check for node.

3. Final Answer:

   It does not handle the case when node has a left subtree -> Option A

4. Quick Check:

   Left subtree check missing for predecessor [OK]

Hint: Check left subtree for predecessor first [OK]

Common Mistakes:

• Ignoring left subtree of node
• Assuming predecessor is always ancestor
• Confusing predecessor with successor logic

5. You want to find the inorder predecessor of a node with value 25 in this BST:

        40
       /  \
     20    60
    /  \  /  \
  10  30 50  70
       /
     25

Which steps correctly find the inorder predecessor of 25?

hard

A. Check left subtree of 25 (none), then move up to ancestors; predecessor is 50

B. Check left subtree of 25 (none), then move up to ancestors; predecessor is 30

C. Check left subtree of 25 (none), then move up to ancestors; predecessor is 10

D. Check left subtree of 25 (none), then move up to ancestors; predecessor is 20

Solution

1. Step 1: Check left subtree of node 25

   Node 25 has no left child, so no predecessor in left subtree.

2. Step 2: Move up to ancestors to find predecessor

   Ancestor nodes smaller than 25 are candidates; 20 is the closest smaller ancestor.

3. Final Answer:

   Check left subtree of 25 (none), then move up to ancestors; predecessor is 20 -> Option D

4. Quick Check:

   Predecessor found by ancestor smaller than node [OK]

Hint: If no left child, predecessor is nearest smaller ancestor [OK]

Common Mistakes:

• Choosing successor instead of predecessor
• Ignoring ancestors when left subtree is empty
• Picking wrong ancestor value