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

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the minimum element in a BST

What is the output of the code when finding the minimum element in the given BST?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def find_min(root):
    current = root
    while current.left is not None:
        current = current.left
    return current.val

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)
root.left.left.left = Node(1)

print(find_min(root))

A 1

B 2

C 5

D 10

💡 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 1.

❓ 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 Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def find_min(root):
    current = root
    while current.left is not None:
        current = current.left
    return current.val

root = Node(3)
root.right = Node(5)
root.right.right = Node(7)

print(find_min(root))

A 5

B None

C 7

D 3

💡 Hint

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

Since there are no left children, the root node value 3 is the smallest.

❓ Predict Output

advanced

Find minimum element after inserting nodes

After inserting nodes into the BST, what is the minimum element found?

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def find_min(root):
    current = root
    while current.left is not None:
        current = current.left
    return current.val

root = None
for v in [20, 10, 30, 5, 15, 3]:
    root = insert(root, v)

print(find_min(root))

A 15

B 5

C 3

D 10

💡 Hint

The smallest inserted value is the minimum.

The smallest value inserted is 3, which is the leftmost node.

🔧 Debug

advanced

Identify the error in this minimum element finder

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

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def find_min(root):
    current = root
    while current.left:
        current = current.right
    return current.val

root = Node(10)
root.left = Node(5)
root.left.left = Node(2)

print(find_min(root))

A Returns wrong minimum value

B AttributeError

C Infinite loop

D None

💡 Hint

Check the direction of traversal inside the loop.

The code moves to the right child while checking for a left child. Since the root has a left child but no right child, current becomes None, and evaluating current.left raises AttributeError.

🧠 Conceptual

expert

Why does finding the minimum element in a BST take O(h) time?

Choose the best explanation for why finding the minimum element in a BST takes time proportional to the tree height h.

A Because we must traverse from root to the leftmost leaf, which can be as long as the height h.

B Because we need to check all nodes in the tree to find the minimum.

C Because the BST is balanced, so height h is always log n, making it constant time.

D Because the minimum element is always at the root, so it takes constant time.

💡 Hint

Think about the path to the smallest value in a BST.

The minimum element is found by going left from the root until no more left child exists, which can be up to height h.

Practice

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

easy

A. At the leftmost node

B. At the rightmost node

C. At the root node

D. At any leaf node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values than their parents, so the smallest value is always towards the left.

2. Step 2: Locate minimum element

   By moving left from the root repeatedly until no more left child exists, we reach the minimum element.

3. Final Answer:

   At the leftmost node -> Option A

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 of the following Python code snippets correctly finds the minimum element in a BST node named root?

easy

A. while root.right is not None:
root = root.right
print(root.val)

B. while root.left is not None:
root = root.left
print(root.val)

C. if root.left is None:
print(root.val)

D. print(min(root.val, root.left.val))

Solution

1. Step 1: Check loop for minimum search

   while root.left is not None: root = root.left print(root.val) correctly moves left while left child exists, which is how to find minimum in BST.

2. Step 2: Verify other options

   while root.right is not None: root = root.right print(root.val) moves right (wrong for minimum), C only checks once, D uses min on values without traversal.

3. Final Answer:

   while root.left is not None: root = root.left print(root.val) -> Option B

4. Quick Check:

   Traverse left until None = while root.left is not None: root = root.left print(root.val) [OK]

Hint: Traverse left child until None to find minimum [OK]

Common Mistakes:

• Traversing right child instead of left
• Not using a loop to reach leftmost node
• Using min() function incorrectly on nodes

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

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def find_min(root):
    while root.left:
        root = root.left
    return root.val

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(2)
root.left.right = Node(7)

print(find_min(root))

medium

A. 5

B. 10

C. 7

D. 2

Solution

1. Step 1: Trace the BST structure

   The tree root is 10, left child 5, left-left child 2, left-right child 7, right child 15.

2. Step 2: Follow find_min function

   The function moves left from 10 to 5, then left again to 2, which has no left child, so returns 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Minimum is leftmost node value, here 2 [OK]

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left-right child as minimum
• Not following loop correctly

4. The following code is intended to find the minimum element in a BST but contains a bug. What is the bug?

def find_min(root):
    while root.right:
        root = root.right
    return root.val

medium

A. It traverses right child instead of left child

B. It returns root.val without checking children

C. It causes infinite loop if root.right is None

D. It does not handle empty tree (None root)

Solution

1. Step 1: Analyze traversal direction

   The code moves to the right child repeatedly, which finds the maximum, not minimum.

2. Step 2: Identify correct traversal for minimum

   Minimum element is found by moving left child repeatedly, so the code should use root.left.

3. Final Answer:

   It traverses right child instead of left child -> Option A

4. Quick Check:

   Minimum = traverse left, not right [OK]

Hint: Minimum is leftmost, so traverse left child [OK]

Common Mistakes:

• Using right child traversal for minimum
• Ignoring empty tree case
• Assuming root is minimum without traversal

5. Given a BST where some nodes may have duplicate values on the left subtree, which approach correctly finds the minimum element?

def find_min(root):
    # Your code here

Choose the correct code snippet to handle duplicates on the left side.

hard

A. while root.right:
root = root.right
return root.val

B. while root.left and root.left.val < root.val:
root = root.left
return root.val

C. while root.left:
root = root.left
return root.val

D. if root.left and root.left.val < root.val:
return find_min(root.left)
return root.val

Solution

1. Step 1: Understand duplicates on left subtree

   In BSTs allowing duplicates on left (e.g., left <= parent), the minimum is always the leftmost node.

2. Step 2: Correct approach

   while root.left: root = root.left return root.val unconditionally traverses left to the leftmost node, handling duplicates correctly.

3. Step 3: Why others fail

   A finds maximum. C and D only traverse if strictly <, stopping early on equal values, missing smaller nodes further left.

4. Final Answer:

   while root.left: root = root.left return root.val -> Option C

5. Quick Check:

   Unconditional left traversal finds min even with duplicates [OK]

Hint: Always traverse left until None, even with duplicates [OK]

Common Mistakes:

• Ignoring duplicates and returning first left child
• Moving right instead of left
• Stopping traversal too early