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.