BST Inorder Predecessor in DSA Go

Mental Model

The inorder predecessor of a node in a BST is the node that comes just before it in sorted order. It is the largest node smaller than the given node.

Analogy: Imagine a sorted list of books on a shelf. The inorder predecessor of a book is the book immediately to its left, the one that comes just before it alphabetically.

      5
     / \
    3   7
   / \   \
  2   4   8
↑curr=5

Dry Run Walkthrough

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

Goal: Find the node that comes just before 5 in sorted order, which is 4

Step 1: Check if node 5 has left child; it does (3), so move to left subtree

      5
     / \
    3↑  7
   / \   \
  2   4   8

Why: Inorder predecessor is the rightmost node in left subtree

Step 2: Move right from 3 to 4, which has no right child

      5
     / \
    3   7
   / \↑  \
  2   4   8

Why: Rightmost node in left subtree is the inorder predecessor

Step 3: Stop at 4 since it has no right child; 4 is predecessor

      5
     / \
    3   7
   / \   \
  2  [4]  8

Why: Found largest node smaller than 5

Result:

4

Annotated Code

DSA Go

package main

import "fmt"

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

func inorderPredecessor(root *TreeNode, p *TreeNode) *TreeNode {
    if p.Left != nil {
        // Move to left subtree
        curr := p.Left
        // Find rightmost node in left subtree
        for curr.Right != nil {
            curr = curr.Right
        }
        return curr
    }
    // If no left subtree, find deepest ancestor where p is in right subtree
    var predecessor *TreeNode
    curr := root
    for curr != nil {
        if p.Val > curr.Val {
            predecessor = curr
            curr = curr.Right
        } else if p.Val < curr.Val {
            curr = curr.Left
        } else {
            break
        }
    }
    return predecessor
}

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

    p := root // node with value 5
    pred := inorderPredecessor(root, p)
    if pred != nil {
        fmt.Printf("Inorder predecessor of %d is %d\n", p.Val, pred.Val)
    } else {
        fmt.Printf("Inorder predecessor of %d does not exist\n", p.Val)
    }
}

if p.Left != nil {

Check if node has left subtree to find predecessor there

curr := p.Left

Start at left child

for curr.Right != nil { curr = curr.Right }

Find rightmost node in left subtree

return curr

Return found predecessor in left subtree

var predecessor *TreeNode curr := root for curr != nil {

If no left subtree, search ancestors for predecessor

if p.Val > curr.Val { predecessor = curr; curr = curr.Right }

Move right and update predecessor when p is greater

else if p.Val < curr.Val { curr = curr.Left }

Move left when p is smaller

else { break }

Stop when node p is found

return predecessor

Return found predecessor or nil if none

Output

Inorder predecessor of 5 is 4

Complexity Analysis

Time: O(h) because we traverse down the tree height h once to find predecessor

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

vs Alternative: Naive approach would do inorder traversal of entire tree O(n), this is faster by using BST properties

Edge Cases

Node has no left subtree and is the smallest node

No predecessor exists, function returns nil

DSA Go

return predecessor

Node has left subtree with multiple nodes

Function finds rightmost node in left subtree correctly

DSA Go

for curr.Right != nil { curr = curr.Right }

Node is root with no left child but has ancestors

Function finds deepest ancestor smaller than node

DSA Go

if p.Val > curr.Val { predecessor = curr; curr = curr.Right }

When to Use This Pattern

When asked to find the previous node in sorted order in a BST, reach for the inorder predecessor pattern because it uses BST structure to find the largest smaller node efficiently.

Common Mistakes

Mistake: Only checking left subtree and ignoring ancestor nodes when no left child exists
Fix: Add logic to traverse from root to find deepest ancestor smaller than target node

Mistake: Returning left child directly without finding rightmost node in left subtree
Fix: Traverse right children in left subtree to find the largest node

Summary

Finds the node just before a given node in BST sorted order.

Use when you need the previous smaller value relative to a node in BST.

If left subtree exists, predecessor is rightmost node there; else, it's deepest ancestor smaller than node.