BST Find Minimum Element in DSA Go

Mental Model

In a binary search tree, the smallest value is always found by going left until no more left child exists.

Analogy: Imagine a family tree where the oldest ancestor is always on the far left branch; to find the oldest, you keep moving left until you can't go further.

    5
   / \
  3   7
 / 
1  
↑

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 1, find minimum element

Goal: Find the smallest value in the BST

Step 1: Start at root node with value 5

5 -> 3 -> 7 -> 1, ↑ at 5

Why: We begin searching from the root to find the minimum

Step 2: Move left to node with value 3

5 -> [3] -> 7 -> 1, ↑ at 3

Why: Minimum is always in the left subtree, so we go left

Step 3: Move left to node with value 1

5 -> 3 -> 7 -> [1], ↑ at 1

Why: Keep moving left to find smaller values

Step 4: No left child from node 1, stop here

5 -> 3 -> 7 -> 1, ↑ at 1

Why: No more left nodes means current node is minimum

Result:

5 -> 3 -> 7 -> 1, minimum element is 1

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
    val   int
    left  *Node
    right *Node
}

func findMin(root *Node) *Node {
    if root == nil {
        return nil
    }
    curr := root
    // move left until no more left child
    for curr.left != nil {
        curr = curr.left
    }
    return curr
}

func main() {
    // Construct BST
    root := &Node{val: 5}
    root.left = &Node{val: 3}
    root.right = &Node{val: 7}
    root.left.left = &Node{val: 1}

    minNode := findMin(root)
    if minNode != nil {
        fmt.Printf("Minimum element is %d\n", minNode.val)
    } else {
        fmt.Println("Tree is empty")
    }
}

curr := root

start from root node

for curr.left != nil {

keep moving left while left child exists

curr = curr.left

advance curr to left child to find smaller value

return curr

return node with no left child as minimum

Output

Minimum element is 1

Complexity Analysis

Time: O(h) because we traverse down the height of the tree following left children

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

vs Alternative: Compared to scanning all nodes (O(n)), this is faster since BST property lets us go directly left

Edge Cases

empty tree

function returns nil indicating no minimum

DSA Go

if root == nil { return nil }

single node tree

returns the single node as minimum

DSA Go

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

When to Use This Pattern

When you need the smallest value in a BST, look for a pattern that moves left until no more left child exists because BST left children hold smaller values.

Common Mistakes

Mistake: Trying to check right children or scanning entire tree for minimum
Fix: Only move left from root until no left child remains

Mistake: Not handling empty tree (nil root) causing runtime errors
Fix: Add a check at start to return nil if root is nil

Summary

Finds the smallest element in a binary search tree by moving left until no left child exists.

Use when you want the minimum value quickly in a BST without scanning all nodes.

The key insight is that the minimum is always the leftmost node in the BST.