BST Inorder Predecessor in DSA C++ - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root node

↓

Search for target node

↓

Found target node?

No→Return None

Yes↓

Does target have left child?

Yes→Go to left child

↓

Go to rightmost node in left subtree

↓

Go up to ancestor where target is in right subtree

↓

Return that ancestor as predecessor

↓

Done

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

Execution Sample

DSA C++

Node* inorderPredecessor(Node* root, Node* target) {
  if (!target) return nullptr;
  if (target->left) {
    Node* curr = target->left;
    while (curr->right) curr = curr->right;
    return curr;
  }
  Node* pred = nullptr;
  Node* curr = root;
  while (curr) {
    if (target->data > curr->data) {
      pred = curr;
      curr = curr->right;
    } else if (target->data < curr->data) {
      curr = curr->left;
    } else break;
  }
  return pred;
}

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

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start search for target 15	10 (root)	pred=nullptr, curr=10	10 / \ 5 15 / \ 12 20
2	15 > 10, move right	15	pred=10, curr=15	10 / \ 5 15 / \ 12 20
3	Found target 15	15	pred=10, curr=15	10 / \ 5 15 / \ 12 20
4	Target has left child 12	15	curr=12	10 / \ 5 15 / \ 12 20
5	Go to rightmost in left subtree	12	curr=12	10 / \ 5 15 / \ 12 20
6	12 has no right child, stop	12	pred=12	10 / \ 5 15 / \ 12 20
7	Return predecessor 12	12	Return 12	10 / \ 5 15 / \ 12 20
8	Example: target 5 no left child	10	pred=nullptr, curr=10	10 / \ 5 15 / \ 12 20
9	5 < 10, move left	5	pred=nullptr, curr=5	10 / \ 5 15 / \ 12 20
10	Found target 5	5	pred=nullptr, curr=5	10 / \ 5 15 / \ 12 20
11	No left child, move up to find ancestor	5	pred=nullptr, curr=10	10 / \ 5 15 / \ 12 20
12	5 < 10, move left	5	pred=nullptr, curr=5	10 / \ 5 15 / \ 12 20
13	No ancestor where target is in right subtree	null	Return nullptr	10 / \ 5 15 / \ 12 20
14	End	null	Stop	Predecessor is nullptr (no predecessor)

💡 Search ends when target found and predecessor identified or none exists.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
curr	10	15	12	12	12
pred	nullptr	10	10	12	12
target	15	15	15	15	15

Key Moments - 3 Insights

Why do we check the left child of the target node first?

Because if the target has a left subtree, the inorder predecessor is the rightmost node in that left subtree, as shown in steps 4-6 in the execution_table.

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

We move up the tree from the root, tracking the last node smaller than the target (pred). This is shown in steps 8-13 where no left child exists.

Why do we update 'pred' only when moving right from current node?

Because moving right means current node is less than target, so it could be a predecessor candidate. This is shown in steps 2 and 11.

Visual Quiz - 3 Questions

Look at the execution_table, what is the predecessor when target is 15 at step 7?

A Node with value 12

B Node with value 10

C Node with value 5

D nullptr

💡 Hint

Check step 7 in execution_table where predecessor is returned as 12.

At which step does the search realize the target 5 has no inorder predecessor?

A Step 9

B Step 11

C Step 13

D Step 14

💡 Hint

Look at step 13 where it returns nullptr because no ancestor is found.

If the target node had no left child but was greater than root, how would 'pred' change during search?

A 'pred' would remain nullptr

B 'pred' would update to root or nodes smaller than target

C 'pred' would update to nodes greater than target

D 'pred' would be set to target node

💡 Hint

Refer to variable_tracker and steps where 'pred' updates when moving right.

Concept Snapshot

BST Inorder Predecessor:
- If target has left child, predecessor = rightmost node in left subtree.
- Else, predecessor = ancestor where target is in right subtree.
- Search from root to find target and track predecessor.
- Return nullptr if no predecessor found.
- Useful for BST deletion and traversal.

Full Transcript

To find the inorder predecessor of a node in a BST, first locate the target node starting from the root. If the target has a left child, the predecessor is the rightmost node in that left subtree. If no left child exists, move up the tree from the root, tracking the last node smaller than the target, which becomes the predecessor. If no such ancestor exists, the predecessor is null. This method helps in BST operations like deletion and inorder traversal.