BST Find Minimum Element in DSA Go - Execution Trace

Concept Flow - BST Find Minimum Element

Start at root

↓

Check if left child exists?

No→Current node is minimum

Yes↓

Move to left child

↓

Repeat check

Start at the root node and keep moving left until no left child exists; that node is the minimum.

Execution Sample

DSA Go

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

This code finds the minimum element in a BST by moving left until no left child is found.

Execution Table

Step	Operation	Current Node	Left Child Exists?	Pointer Changes	Visual State
1	Start at root	20	Yes	current = root (20)	20 / \ 10 30
2	Check left child	20	Yes	Move current to left child (10)	20 / \ 10 30
3	Check left child	10	Yes	Move current to left child (5)	20 / \ 10 30 / 5
4	Check left child	5	No	Stop, current is minimum	20 / \ 10 30 / 5
5	Return current	5	No	Return node with value 5	Minimum element found: 5

💡 Left child does not exist at node 5, so 5 is the minimum element.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current	20 (root)	10	5	5	5

Key Moments - 3 Insights

Why do we keep moving to the left child to find the minimum?

Because in a BST, all smaller values are on the left. The execution_table rows 2 and 3 show moving left to smaller nodes until no left child exists.

What if the root has no left child?

Then the root itself is the minimum. The execution_table row 1 shows the root node with a left child, but if it had none, we would stop immediately as in row 4.

Why do we stop when current.Left is nil?

Because no smaller node exists to the left. The execution_table row 4 shows this stopping condition.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' after step 3?

A 5

B 10

C 20

D 30

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns at step 3.

At which step does the condition 'Left Child Exists?' become false?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Left Child Exists?' column to find when it changes to 'No'.

If the root node had no left child, what would be the minimum element?

A The left child of root

B The right child of root

C The root node itself

D No minimum element

💡 Hint

Refer to the key moment about root having no left child and the execution_table row 4.

Concept Snapshot

BST Find Minimum Element:
- Start at root node
- While left child exists, move left
- When no left child, current node is minimum
- Return current node
- Works because BST left subtree has smaller values

Full Transcript

To find the minimum element in a Binary Search Tree (BST), start at the root node. Check if the current node has a left child. If yes, move to that left child. Repeat this process until you reach a node with no left child. This node is the minimum element in the BST. The code uses a loop to move left until current.Left is nil, then returns the current node. This works because in BSTs, smaller values are always to the left. If the root has no left child, the root itself is the minimum. The execution table shows each step with the current node and pointer changes, confirming the minimum found.

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