BST Find Minimum Element in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A Binary Search Tree is a tree data structure where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater than the parent's value.

beginner

In a BST, where is the minimum element located?

The minimum element is located at the leftmost node of the BST because all smaller values are stored to the left.

beginner

What is the basic approach to find the minimum element in a BST?

Start from the root and keep moving to the left child until you reach a node with no left child. That node contains the minimum value.

intermediate

Why is finding the minimum element in a BST efficient?

Because you only traverse down the left children, the time complexity is O(h), where h is the height of the tree, which is efficient compared to searching all nodes.

beginner

What happens if the BST is empty when trying to find the minimum element?

If the BST is empty (root is nil), there is no minimum element, and the function should handle this case gracefully, often by returning nil or an error.

Where do you find the minimum element in a BST?

A At the root node

B At the rightmost node

C At the leftmost node

D At any leaf node

The minimum element is always at the leftmost node in a BST.

What is the time complexity to find the minimum element in a BST?

A O(h)

B O(log n)

C O(n)

D O(1)

Finding the minimum element requires traversing down the left children, which takes O(h) time, where h is the height of the tree.

What should a function return if the BST is empty when finding the minimum element?

A Nil or an error

B The maximum element

C The root node

D Zero

If the BST is empty, there is no minimum element, so the function should return nil or an error.

Which direction do you move to find the minimum element in a BST?

A Right

B Left

C Up

D Down

You move left repeatedly to find the minimum element in a BST.

If a BST has only one node, what is the minimum element?

A The right child

B No minimum element

C The left child

D The root node itself

If there is only one node, that node is the minimum element.

Explain how to find the minimum element in a Binary Search Tree.

Think about the BST property and where smaller values are stored.

What should you consider when implementing a function to find the minimum element in a BST?

Consider edge cases and traversal logic.

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