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.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the largest key smaller than the given node's key

B. The node with the smallest key greater than the given node's key

C. The root node of the BST

D. The left child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node with a key greater than the current node's key.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option B

4. Quick Check:

   Inorder successor = next larger node [OK]

Hint: Inorder successor is next bigger node in BST [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Assuming successor is parent node

2. Which of the following Go function signatures correctly represents a function to find the inorder successor of a BST node?

easy

A. func inorderSuccessor(root *Node, p *Node) *Node

B. func inorderSuccessor(p *Node) *Node

C. func inorderSuccessor(root Node, p Node) Node

D. func inorderSuccessor(root *Node) int

Solution

1. Step 1: Analyze function parameters

   To find the inorder successor, we need the BST root and the target node pointer, both as pointers to Node structs.

2. Step 2: Check return type

   The function should return a pointer to the successor node, so return type is *Node.

3. Final Answer:

   func inorderSuccessor(root *Node, p *Node) *Node -> Option A

4. Quick Check:

   Function needs root and target node pointers, returns node pointer [OK]

Hint: Function needs root and target node pointers [OK]

Common Mistakes:

• Passing nodes by value instead of pointer
• Returning int instead of node pointer
• Missing root parameter

3. Given the following BST and code snippet, what will be printed?

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

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

// BST structure:
//       20
//      /  \
//    10    30
//      \
//      15

p := &Node{Val: 15}
succ := inorderSuccessor(root, p)
if succ != nil {
    fmt.Println(succ.Val)
} else {
    fmt.Println("nil")
}

medium

A. 20

B. 30

C. 15

D. nil

Solution

1. Step 1: Trace inorderSuccessor function for p=15

   Start at root=20: 15 < 20, successor=20, move left to 10. At 10: 15 >= 10, move right to 15. At 15: 15 >= 15, move right (nil). Loop ends.

2. Step 2: Return successor node

   Successor is 20, so succ.Val = 20 is printed.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Next bigger node after 15 is 20 [OK]

Hint: Successor is smallest node bigger than p [OK]

Common Mistakes:

• Returning p itself as successor
• Returning nil when right subtree is empty
• Confusing successor with predecessor

4. The following Go code tries to find the inorder successor of a node in a BST but has a bug. What is the bug?

func inorderSuccessor(root, p *Node) *Node {
    if p.Right != nil {
        curr := p.Right
        for curr.Left != nil {
            curr = curr.Left
        }
        return curr
    }
    var successor *Node
    for root != nil {
        if p.Val < root.Val {
            successor = root
            root = root.Left
        } else {
            root = root.Right
        }
    }
    return successor
}

medium

A. It does not handle the case when p has no right child

B. It incorrectly returns p.Right when p.Right is nil

C. It does not update successor when p.Val equals root.Val

D. It assumes root is always the BST root, which may not be true

Solution

1. Step 1: Understand the logic for successor search

   The code tries to find successor by checking right subtree or walking from root to find successor.

2. Step 2: Identify the bug in root traversal

   The code assumes root is the BST root, but if root is not the actual BST root or p is not reachable from root, the successor found may be incorrect.

3. Final Answer:

   It assumes root is always the BST root, which may not be true -> Option D

4. Quick Check:

   Root must be BST root to find correct successor [OK]

Hint: Ensure root is BST root, not arbitrary node [OK]

Common Mistakes:

• Passing a root that is not the BST root
• Not checking if p.Right is nil before access
• Ignoring case when p has no right subtree

5. You have a BST where each node has a parent pointer in addition to left and right children. How can you find the inorder successor of a node p efficiently using this parent pointer? Choose the correct approach.

hard

A. Always move to the root and perform full inorder traversal to find successor

B. If p has left child, successor is rightmost node in left subtree; else move down to left child

C. If p has right child, successor is leftmost node in right subtree; else move up using parent until node is left child of its parent

D. Successor is always the parent node regardless of children

Solution

1. Step 1: Check if p has right child

   If yes, successor is the leftmost node in p's right subtree.

2. Step 2: If no right child, move up using parent pointer

   Keep moving up until current node is left child of its parent; that parent is the successor.

3. Final Answer:

   If p has right child, successor is leftmost node in right subtree; else move up using parent until node is left child of its parent -> Option C

4. Quick Check:

   Use right subtree or climb parents to find successor [OK]

Hint: Use right subtree or climb parents via left child check [OK]

Common Mistakes:

• Confusing left and right subtree roles
• Always returning parent as successor
• Performing full traversal instead of using parent pointer