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.