BST Inorder Predecessor in DSA Go - Execution Trace

Concept Flow - BST Inorder Predecessor

Start at root

↓

Search for node with given key

↓

Node found?

No→Return nil (no predecessor)

Yes↓

Does node have left child?

Yes→Go to left child

↓

Go to rightmost node in left subtree

↓

This is inorder predecessor

No↓

Go up to ancestor where node is in right subtree

↓

That ancestor is inorder predecessor

↓

Return predecessor node

Find the node with the given key, then find its inorder predecessor by either going to the rightmost node in its left subtree or moving up to the nearest ancestor where the node is in the right subtree.

Execution Sample

DSA Go

func inorderPredecessor(root, key *Node) *Node {
  node := search(root, key.val)
  if node == nil {
    return nil
  }
  if node.left != nil {
    return rightmost(node.left)
  }
  return ancestorPredecessor(root, node)
}

This code finds the inorder predecessor of a node in a BST by searching the node, then checking its left subtree or ancestors.

Execution Table

Step	Operation	Node Visited	Pointer Changes	Visual State
1	Start at root	50	head=root(50)	50 / \ 30 70 / \ / \ 20 40 60 80
2	Search for node with key=40	50	current=50	Same as above
3	Move left (40 < 50)	30	current=30	Same as above
4	Move right (40 > 30)	40	current=40	Same as above
5	Node found	40	node=40	Same as above
6	Check if node.left exists	40	node.left=nil	Same as above
7	No left child, find ancestor predecessor	40	start=root(50)	Same as above
8	Move down from root to find ancestor	50	predecessor=nil	Same as above
9	40 < 50, move left	30	predecessor=nil	Same as above
10	40 > 30, set predecessor=30, move right	40	predecessor=30	Same as above
11	Reached node, stop	40	predecessor=30	Same as above
12	Return predecessor node	30	return 30	Same as above

💡 Node 40 has no left child; predecessor is ancestor 30 found by moving up.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 10	Final
current	root(50)	50	30	40	40	40	40	40
node	nil	nil	nil	nil	40	40	40	40
predecessor	nil	nil	nil	nil	nil	nil	30	30

Key Moments - 3 Insights

Why do we check if the node has a left child first?

Because if the node has a left child, its inorder predecessor is the rightmost node in that left subtree (see step 6 and 7). If no left child, we look for ancestor predecessor.

Why do we move up to ancestors when there is no left child?

Because the inorder predecessor is the nearest ancestor where the node lies in the right subtree (see steps 7 to 11). This ancestor is the predecessor.

Why do we stop searching ancestor when we reach the node itself?

Because once we reach the node during ancestor traversal, we have found the predecessor stored in 'predecessor' variable (step 11).

Visual Quiz - 3 Questions

Look at the execution table, what is the value of 'predecessor' after step 10?

A 30

B 40

C 50

D nil

💡 Hint

Check the 'predecessor' column in variable_tracker after step 10.

At which step do we confirm that the node has no left child?

A Step 5

B Step 6

C Step 7

D Step 10

💡 Hint

Look at the 'Operation' column in execution_table where left child check happens.

If the node had a left child, which step would we go to next?

A Step 7

B Step 6

C Step 4

D Step 12

💡 Hint

Refer to the decision at step 6 in execution_table about left child presence.

Concept Snapshot

BST Inorder Predecessor:
- Find node with given key.
- If node has left child, predecessor is rightmost node in left subtree.
- Else, predecessor is nearest ancestor where node is in right subtree.
- Return predecessor node or nil if none.
- Used in BST deletion and traversal.

Full Transcript

To find the inorder predecessor in a BST, first search for the node with the given key starting from the root. If the node is found and has a left child, the predecessor is the rightmost node in its left subtree. If there is no left child, move up the tree to find the nearest ancestor where the node lies in the right subtree; that ancestor is the predecessor. If no such ancestor exists, the node has no inorder predecessor. This process is shown step-by-step in the execution table and variable tracker.