BST Inorder Successor in DSA Go

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node greater than the given node.

Analogy: Imagine a line of people sorted by height. The inorder successor is the person who is just a bit taller than you, standing immediately after you in line.

       5
      / \
     3   7
    / \   \
   2   4   8

Node: 4
Inorder successor: 5

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder successor of node 4

Goal: Find the node that comes immediately after 4 in sorted order

Step 1: Check if node 4 has right child

Node 4 has no right child

Why: If right child exists, successor is leftmost node in right subtree

Step 2: Start from root (5), track potential successor

Current node: 5, potential successor: null

Why: We look for a node greater than 4 to update successor

Step 3: Since 4 < 5, update successor to 5 and move left

Current node: 3, potential successor: 5

Why: 3 is less than 4, so move right to find 4

Step 4: Since 4 > 3, move right to node 4

Current node: 4, potential successor: 5

Why: We found the node 4

Step 5: No right child, return potential successor 5

Successor found: 5

Why: 5 is the smallest node greater than 4

Result:

Successor of 4 is 5

Annotated Code

DSA Go

package main

import "fmt"

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

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	// If right child exists, go to leftmost node in right subtree
	if p.Right != nil {
		curr := p.Right
		for curr.Left != nil {
			curr = curr.Left // advance to leftmost node
		}
		return curr
	}

	// Otherwise, start from root and track successor
	var successor *TreeNode
	curr := root
	for curr != nil {
		if p.Val < curr.Val {
			successor = curr // update successor
			curr = curr.Left // move left to find smaller successor
		} else {
			curr = curr.Right // move right to find p
		}
	}
	return successor
}

func main() {
	// Build BST
	root := &TreeNode{5, nil, nil}
	root.Left = &TreeNode{3, nil, nil}
	root.Right = &TreeNode{7, nil, nil}
	root.Left.Left = &TreeNode{2, nil, nil}
	root.Left.Right = &TreeNode{4, nil, nil}
	root.Right.Right = &TreeNode{8, nil, nil}

	p := root.Left.Right // node with value 4
	succ := inorderSuccessor(root, p)
	if succ != nil {
		fmt.Printf("Successor of %d is %d\n", p.Val, succ.Val)
	} else {
		fmt.Printf("No successor for %d\n", p.Val)
	}
}

if p.Right != nil {

Check if node has right subtree to find successor there

for curr.Left != nil {

Traverse to leftmost node in right subtree for smallest greater value

var successor *TreeNode

Initialize variable to track potential successor

for curr != nil {

Traverse tree from root to find successor by comparing values

if p.Val < curr.Val {

If current node value greater than p, update successor and go left

else { curr = curr.Right }

If current node value less or equal, go right to find p

Output

Successor of 4 is 5

Complexity Analysis

Time: O(h) because we traverse from root down to leaf where h is tree height

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach does inorder traversal O(n) and stores nodes, which uses O(n) time and space; this method is more efficient

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA Go

if p.Right != nil {

Node has no right subtree and is the largest node

No successor found, function returns nil

DSA Go

return successor

Node is root with no right child

Successor is ancestor with greater value if exists

DSA Go

if p.Val < curr.Val {

When to Use This Pattern

When asked to find the next bigger node in a BST, use the inorder successor pattern because it leverages BST properties to find the answer efficiently.

Common Mistakes

Mistake: Not checking if the node has a right subtree first
Fix: Always check right subtree first to find successor quickly if it exists

Mistake: Not updating successor when moving left from root
Fix: Update successor when current node value is greater than target node value

Summary

Finds the next node in sorted order after a given node in a BST.

Use when you need the immediate larger value than a given node in a BST.

If node has right child, successor is leftmost node there; else track ancestor with greater value.

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