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.

Practice

1. In a Binary Search Tree (BST), where is the minimum element always located?

easy

A. At the root node

B. At the rightmost node

C. At any leaf node

D. At the leftmost node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values than their parents.

2. Step 2: Locate minimum element

   The smallest value is found by going as far left as possible from the root.

3. Final Answer:

   At the leftmost node -> Option D

4. Quick Check:

   Minimum element = leftmost node [OK]

Hint: Minimum is always the leftmost node in BST [OK]

Common Mistakes:

• Confusing minimum with root node
• Thinking minimum is at rightmost node
• Assuming minimum can be any leaf

2. Which Go code snippet correctly finds the minimum element in a BST node structure defined as type Node struct { Val int; Left, Right *Node }?

easy

A. func findMin(root *Node) int { for root.Right != nil { root = root.Right } return root.Val }

B. func findMin(root *Node) int { for root.Left != nil { root = root.Left } return root.Val }

C. func findMin(root *Node) int { return root.Val }

D. func findMin(root *Node) int { if root == nil { return 0 } return root.Right.Val }

Solution

1. Step 1: Check loop direction

   To find minimum, traverse left child nodes until none left.

2. Step 2: Verify return value

   Return the value of the last leftmost node found.

3. Final Answer:

   func findMin(root *Node) int { for root.Left != nil { root = root.Left } return root.Val } -> Option B

4. Quick Check:

   Traverse left until nil, then return value [OK]

Hint: Loop left child until nil, then return node value [OK]

Common Mistakes:

• Looping right child instead of left
• Returning root value without traversal
• Accessing right child value incorrectly

3. What will be the output of the following Go code snippet?

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

func findMin(root *Node) int {
  for root.Left != nil {
    root = root.Left
  }
  return root.Val
}

func main() {
  root := &Node{Val: 10}
  root.Left = &Node{Val: 5}
  root.Right = &Node{Val: 15}
  root.Left.Left = &Node{Val: 2}
  root.Left.Right = &Node{Val: 7}
  fmt.Println(findMin(root))
}

medium

A. 2

B. 5

C. 7

D. 10

Solution

1. Step 1: Trace the BST structure

   The leftmost node is root.Left.Left with value 2.

2. Step 2: Apply findMin function

   Function moves left until no more left child, returns 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Output is value of leftmost node in BST [OK]

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left and right child nodes
• Misreading tree structure

4. Identify the bug in this Go function that tries to find the minimum element in a BST:

func findMin(root *Node) int {
  if root == nil {
    return 0
  }
  for root.Right != nil {
    root = root.Right
  }
  return root.Val
}

medium

A. It should traverse left child nodes, not right

B. It should return 0 only if root.Val is 0

C. It should check for root.Left == nil before loop

D. It should return root.Left.Val instead of root.Val

Solution

1. Step 1: Analyze traversal direction

   Minimum element is found by going left, not right.

2. Step 2: Identify correct loop condition

   Loop should check root.Left != nil, not root.Right.

3. Final Answer:

   It should traverse left child nodes, not right -> Option A

4. Quick Check:

   Minimum = leftmost node, so traverse left [OK]

Hint: Traverse left children to find minimum, not right [OK]

Common Mistakes:

• Looping right child instead of left
• Returning 0 incorrectly for nil root
• Returning wrong node value

5. Given a BST where some nodes may have duplicate values, which approach correctly finds the minimum element considering duplicates are always inserted to the right subtree?

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

func findMin(root *Node) int {
  // Your code here
}

medium

A. Traverse left child nodes until nil, but skip nodes equal to parent value

B. Traverse right child nodes until nil, then return node value

C. Traverse left child nodes until nil, then return node value

D. Traverse left child nodes until nil, return the smallest value found including duplicates

Solution

1. Step 1: Understand duplicate insertion rule

   Duplicates go to right subtree, so left subtree has strictly smaller values.

2. Step 2: Find minimum including duplicates

   Minimum is still the leftmost node; duplicates do not affect left subtree.

3. Step 3: Return smallest value found at leftmost node

   Traverse left child nodes until nil, then return node value.

4. Final Answer:

   Traverse left child nodes until nil, then return node value -> Option C

5. Quick Check:

   Minimum = leftmost node including duplicates [OK]

Hint: Duplicates on right don't affect leftmost minimum [OK]

Common Mistakes:

• Skipping nodes equal to parent value incorrectly
• Traversing right subtree for minimum
• Ignoring duplicates in minimum search