Why BST Inorder Predecessor in DSA Typescript?

The Big Idea

Discover how to find the 'just before' value in a tree without checking every node!

The Scenario

Imagine you have a family tree drawn on paper, and you want to find the person who comes just before someone in the family order. Doing this by looking at every name and comparing takes a lot of time and can get confusing.

The Problem

Manually searching for the person just before another means checking many names one by one. This is slow and easy to make mistakes, especially if the tree is big or not sorted well.

The Solution

The BST Inorder Predecessor helps find the immediate previous value in a sorted tree quickly by following a clear path, avoiding unnecessary checks and mistakes.

Before vs After

✗ Before

function findPredecessor(root, target) {
  let values = [];
  inorderTraversal(root, values);
  for (let i = 1; i < values.length; i++) {
    if (values[i] === target) return values[i - 1];
  }
  return null;
}

✓ After

function findInorderPredecessor(root, target) {
  let predecessor = null;
  let current = root;
  while (current) {
    if (target > current.value) {
      predecessor = current;
      current = current.right;
    } else {
      current = current.left;
    }
  }
  return predecessor ? predecessor.value : null;
}

What It Enables

This lets you quickly find the closest smaller value in a sorted tree, making searches and updates much faster and more reliable.

Real Life Example

In a contact list sorted by names, finding the contact that comes just before a given name helps in quick navigation and suggestions.

Key Takeaways

Manual search is slow and error-prone for finding previous values.

BST Inorder Predecessor uses tree properties to find the answer efficiently.

This improves speed and accuracy in sorted data operations.

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