BST Inorder Successor in DSA Go - Execution Trace

Concept Flow - BST Inorder Successor

Start at root node

↓

Search for target node

↓

Found target node?

No→Return None

Yes↓

Does target have right child?

Yes→Go to right child

↓

Go left as far as possible

↓

Go up to parent until node is left child

↓

Return found successor or None

Find the inorder successor by first locating the target node, then either going to its right subtree's leftmost node or moving up to find the nearest ancestor where target is in left subtree.

Execution Sample

DSA Go

func inorderSuccessor(root, p *TreeNode) *TreeNode {
    if p.Right != nil {
        p = p.Right
        for p.Left != nil {
            p = p.Left
        }
        return p
    }
    var succ *TreeNode
    for root != nil {
        if p.Val < root.Val {
            succ = root
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return succ
}

This code finds the inorder successor of node p in a BST by checking right subtree or moving up ancestors.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root to find target	10	None	10 / \ 5 15 / \ \ 3 7 18
2	Compare p.Val=7 with root.Val=10	10	Move root to left child	10 / \ 5 15 / \ \ 3 7 18
3	Compare p.Val=7 with root.Val=5	5	Move root to right child	10 / \ 5 15 / \ \ 3 7 18
4	Compare p.Val=7 with root.Val=7	7	Found target node	10 / \ 5 15 / \ \ 3 7 18
5	Check if p.Right exists	7	p.Right is nil	7 has no right child
6	Move root to 10 to find successor	10	succ = 10, root = root.Left (5)	10 / \ 5 15 / \ \ 3 7 18
7	p.Val=7 < root.Val=10	10	succ = 10, root = root.Left (5)	succ=10
8	p.Val=7 > root.Val=5	5	root = root.Right (7)	succ=10
9	p.Val=7 == root.Val=7	7	root = root.Right (nil)	succ=10
10	root is nil, stop	nil	Return succ=10	Successor is 10

💡 Traversal ends when root becomes nil; successor found or nil if none.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	Final
root.Val	10	5	7	7	10	5	7	nil	nil
succ.Val	nil	nil	nil	nil	10	10	10	10	10
p.Val	7	7	7	7	7	7	7	7	7

Key Moments - 3 Insights

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

Because if the target has a right child, the inorder successor is the leftmost node in that right subtree (see step 5 and 6 in execution_table).

Why do we move up to ancestors when the target has no right child?

Because the successor is the nearest ancestor for which the target node lies in its left subtree (see steps 6 to 10 where succ is updated).

Why does the traversal stop when root becomes nil?

Because we have exhausted the path to find a successor; if none found, successor is nil (step 10).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is true about node 7?

A Node 7 has a right child

B Node 7 has no right child

C Node 7 is the root

D Node 7 is the successor

💡 Hint

Check the 'Operation' and 'Pointer Changes' columns at step 5 in execution_table

At which step does the successor get assigned to node 10?

A Step 4

B Step 8

C Step 6

D Step 10

💡 Hint

Look at the 'Pointer Changes' column where succ is first set

If node 7 had a right child, how would the execution_table change?

A We would go to the right child and find its leftmost node as successor

B We would move up to ancestors instead

C The successor would be nil immediately

D The traversal would stop at root

💡 Hint

Refer to the concept_flow where right child presence leads to leftmost node search

Concept Snapshot

BST Inorder Successor:
- If node has right child, successor = leftmost node in right subtree
- Else, successor = nearest ancestor where node is in left subtree
- Search target node first, then apply above
- Returns nil if no successor exists

Full Transcript

To find the inorder successor in a BST, first locate the target node. If it has a right child, go to that right child and then keep going left until no more left children exist; that node is the successor. If no right child exists, move up the tree from the root, tracking the last node where you took a left turn; that node is the successor. If no such node exists, the successor is nil. This process ensures the next larger node in sorted order is found.