BST Inorder Predecessor in DSA Typescript - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root

↓

Find node with given key

↓

Does node have left child?

No→Go up to ancestors

↓

Find ancestor where node is in right subtree

↓

Go to left child

↓

Go to rightmost node in left subtree

↓

This node is inorder predecessor

↓

Done

Start from root, find the node. If it has a left child, go left then rightmost to find predecessor. Otherwise, go up ancestors to find where node is in right subtree.

Execution Sample

DSA Typescript

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

Finds the inorder predecessor of a node with given key in a BST by checking left subtree or ancestors.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root to find node with key=15	10	node = root (10), predecessor = null	10 / \ 5 15 / \ 12 20
2	Key 15 > 10, go right	15	node = node.right (15)	10 / \ 5 15 / \ 12 20
3	Found node with key=15	15	node found	10 / \ 5 15 / \ 12 20
4	Node has left child? Yes (12)	15	predecessor = node.left (12)	10 / \ 5 15 / \ 12 20
5	Go to rightmost node in left subtree of 15	12	predecessor = 12 (no right child)	10 / \ 5 15 / \ 12 20
6	Rightmost node in left subtree is 12, return as predecessor	12	return predecessor = 12	10 / \ 5 15 / \ 12 20

💡 Predecessor found as rightmost node in left subtree of node 15

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 4	After Step 5	Final
node	root (10)	10	15	15	15	15
predecessor	null	null	null	12	12	12

Key Moments - 3 Insights

Why do we go to the rightmost node in the left subtree to find the predecessor?

Because the inorder predecessor is the largest value smaller than the node, which is the rightmost node in its left subtree as shown in execution_table step 5.

What if the node has no left child? How do we find the predecessor?

Then we look up to ancestors to find the nearest ancestor where the node is in the right subtree, as described in concept_flow and would be shown if node.left was null.

Why do we stop searching when node.val === key?

Because we found the exact node whose predecessor we want, as shown in execution_table step 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the value of 'node'?

A 15

B 10

C 12

D null

💡 Hint

Check the 'Current Node' column at step 2 in execution_table.

At which step does the algorithm decide the predecessor is the rightmost node in the left subtree?

A Step 3

B Step 1

C Step 5

D Step 6

💡 Hint

Look at the 'Operation' column describing going to the rightmost node in left subtree.

If the node with key 15 had no left child, what would the algorithm do next?

A Return null immediately

B Traverse ancestors to find predecessor

C Go to right child of node 15

D Go to left child of root

💡 Hint

Refer to concept_flow where no left child leads to checking ancestors.

Concept Snapshot

BST Inorder Predecessor:
- Find node with given key.
- If node has left child, predecessor = rightmost node in left subtree.
- Else, predecessor = nearest ancestor where node is in right subtree.
- Returns null if no predecessor.
- Used in BST deletion and traversal.

Full Transcript

To find the inorder predecessor in a BST, start at the root and search for the node with the given key. Once found, check if it has a left child. If yes, move to the left child and then go as far right as possible to find the predecessor. If no left child exists, move up the tree to find the closest ancestor where the node lies in the right subtree. This ancestor is the predecessor. The execution table shows step-by-step how the node is found and how the predecessor is determined by moving to the left subtree's rightmost node. Variables 'node' and 'predecessor' track the current node and candidate predecessor during the process. Key moments clarify why the rightmost node in the left subtree is chosen and what happens if no left child exists. The visual quiz tests understanding of these steps. This method is essential for BST operations like deletion and inorder traversal.

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