BST Find Minimum Element in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find minimum element in a BST

What is the output of this Go code that finds the minimum element in a binary search tree?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func findMin(root *Node) int {
    current := root
    for current.Left != nil {
        current = current.Left
    }
    return current.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))
}

A 10

B 2

C 7

D 5

💡 Hint

The minimum element in a BST is the leftmost node.

The function moves left until it finds the leftmost node, which has the smallest value. Here, that value is 2.

❓ Predict Output

intermediate

Minimum element in a BST with only right children

What will the output be when finding the minimum element in this BST where all nodes only have right children?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func findMin(root *Node) int {
    current := root
    for current.Left != nil {
        current = current.Left
    }
    return current.Val
}
func main() {
    root := &Node{Val: 3}
    root.Right = &Node{Val: 6}
    root.Right.Right = &Node{Val: 9}
    fmt.Println(findMin(root))
}

A 9

B 6

C 3

D 0

💡 Hint

If there is no left child, the root is the minimum.

Since no node has a left child, the root node value 3 is the minimum.

🔧 Debug

advanced

Identify the error in this BST minimum finder

What error will this Go code produce when trying to find the minimum element in a BST?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func findMin(root *Node) int {
    current := root
    for current != nil {
        current = current.Left
    }
    return current.Val
}
func main() {
    root := &Node{Val: 8}
    root.Left = &Node{Val: 3}
    root.Left.Left = &Node{Val: 1}
    fmt.Println(findMin(root))
}

A 1

B 8

C 0

D runtime error: invalid memory address or nil pointer dereference

💡 Hint

Check what happens after the loop ends.

The loop continues until current is nil, then tries to access current.Val causing a nil pointer dereference.

🧠 Conceptual

advanced

Why does the minimum element lie in the left subtree in a BST?

Which option best explains why the minimum element in a binary search tree is always found by going left until no more left child exists?

A Because in a BST, left children are always smaller than their parent nodes, so the leftmost node is the smallest.

B Because right children are always smaller than their parent nodes, so the minimum is on the right.

C Because the root node always contains the minimum value in a BST.

D Because the minimum value is always stored in the rightmost leaf node.

💡 Hint

Recall the BST property about left and right children values.

By definition, in a BST, left children have smaller values than their parents, so the smallest value is found by going left as far as possible.

❓ Predict Output

expert

Output of recursive minimum finder in BST

What is the output of this recursive Go function that finds the minimum element in a BST?

DSA Go

package main
import "fmt"
type Node struct {
    Val   int
    Left  *Node
    Right *Node
}
func findMinRecursive(root *Node) int {
    if root.Left == nil {
        return root.Val
    }
    return findMinRecursive(root.Left)
}
func main() {
    root := &Node{Val: 20}
    root.Left = &Node{Val: 10}
    root.Left.Left = &Node{Val: 5}
    root.Left.Left.Left = &Node{Val: 2}
    root.Right = &Node{Val: 30}
    fmt.Println(findMinRecursive(root))
}

A 2

B 5

C 10

D 20

💡 Hint

The function calls itself on the left child until no left child exists.

The recursion goes down the left children until it reaches the leftmost node with value 2, which it returns.

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