BST Find Minimum Element in DSA Go - Build from Scratch

BST Find Minimum Element

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the smallest number in the tree. This is useful when you want to quickly find the minimum value in a sorted structure.

🎯 Goal: Build a simple BST with a few nodes, then write code to find and print the minimum element in the BST.

📋 What You'll Learn

Create a BST node structure with integer values

Insert nodes to form a BST with these exact values: 15, 10, 20, 8, 12

Write a function to find the minimum element in the BST

Print the minimum element found

💡 Why This Matters

🌍 Real World

Finding minimum or maximum values quickly is important in many applications like databases, scheduling, and priority queues.

💼 Career

Understanding BST operations is fundamental for software engineers working with data structures, algorithms, and performance optimization.

1

Create BST Node Structure and Insert Nodes

Create a struct called Node with an int field called value and two pointers called left and right of type *Node. Then create a variable called root and assign it a pointer to a Node with value 15. Next, manually create and link nodes with values 10, 20, 8, and 12 to form the BST exactly as follows: 15 is root, 10 is left child of 15, 20 is right child of 15, 8 is left child of 10, and 12 is right child of 10.

DSA Go

// Your code here

Hint

Define the Node struct first. Then create root and assign child nodes by setting root.left, root.right, and so on.

2

Create a Function to Find Minimum Element

Create a function called findMin that takes a pointer to Node called root and returns an int. Inside the function, use a variable called current to traverse the tree starting from root. Move current to its left child repeatedly until current.left is nil. Then return current.value as the minimum element.

DSA Go

package main

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

func main() {
    root := &Node{value: 15}
    root.left = &Node{value: 10}
    root.right = &Node{value: 20}
    root.left.left = &Node{value: 8}
    root.left.right = &Node{value: 12}
}

// Create function findMin with parameter root *Node returning int
// Your code here

Hint

Use a for loop to keep moving left until no more left child exists.

3

Call findMin Function in main

Inside the main function, call the findMin function with root as argument and assign the result to a variable called minValue.

DSA Go

package main

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

func findMin(root *Node) int {
    current := root
    for current.left != nil {
        current = current.left
    }
    return current.value
}

func main() {
    root := &Node{value: 15}
    root.left = &Node{value: 10}
    root.right = &Node{value: 20}
    root.left.left = &Node{value: 8}
    root.left.right = &Node{value: 12}

    // Call findMin with root and assign to minValue
    // Your code here
}

Hint

Assign the result of findMin(root) to minValue.

4

Print the Minimum Element

Add a fmt.Println statement in main to print the text "Minimum element:" followed by the value of minValue.

DSA Go

package main

import "fmt"

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

func findMin(root *Node) int {
    current := root
    for current.left != nil {
        current = current.left
    }
    return current.value
}

func main() {
    root := &Node{value: 15}
    root.left = &Node{value: 10}
    root.right = &Node{value: 20}
    root.left.left = &Node{value: 8}
    root.left.right = &Node{value: 12}

    minValue := findMin(root)

    // Print "Minimum element:" and minValue
    // Your code here
}

Hint

Use fmt.Println("Minimum element:", minValue) to print the result.

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