BST Find Minimum Element in DSA Java

Mental Model

In a binary search tree, the smallest value is always found by going left until you can't go left anymore.

Analogy: Imagine a tree where smaller numbers are always on the left side. To find the smallest number, you keep walking left until you reach the end.

      10
     /  \
    5    15
   / \     
  2   7    
 ↑       
(root)

Dry Run Walkthrough

Input: BST: 10 -> 5 -> 15 -> 2 -> 7; find minimum element

Goal: Find the smallest value in the BST by moving left until no more left child exists

Step 1: Start at root node with value 10

10 -> 5 -> 15 -> 2 -> 7, current = 10 ↑

Why: We begin search from the root to find the minimum

Step 2: Move current to left child 5

10 -> [5 ↑] -> 15 -> 2 -> 7

Why: Smaller values are on the left, so we go left to find smaller

Step 3: Move current to left child 2

10 -> 5 -> [2 ↑] -> 7 -> 15

Why: Keep moving left to find the smallest value

Step 4: No left child of 2, stop here

10 -> 5 -> 2 ↑ -> 7 -> 15

Why: No more left nodes means current node is minimum

Result:

Minimum element is 2

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class BSTFindMin {
    // Find minimum value in BST
    public static int findMin(Node root) {
        if (root == null) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node current = root;
        // Move left until no left child
        while (current.left != null) {
            current = current.left;
        }
        return current.val;
    }

    public static void main(String[] args) {
        // Build BST
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.left.left = new Node(2);
        root.left.right = new Node(7);

        int min = findMin(root);
        System.out.println("Minimum element is " + min);
    }
}

Node current = root;

Start from root node to begin search

while (current.left != null) {

Keep moving left while left child exists

current = current.left;

Advance current to left child to find smaller value

return current.val;

Return value of leftmost node as minimum

Output

Minimum element is 2

Complexity Analysis

Time: O(h) because we only traverse down the left edge where h is the tree height

Space: O(1) because we use only a few variables and no extra data structures

vs Alternative: Compared to scanning all nodes (O(n)), this is faster since BST property lets us go directly left

Edge Cases

Empty BST

Throws IllegalArgumentException to indicate no minimum

DSA Java

if (root == null) { throw new IllegalArgumentException("BST is empty"); }

BST with single node

Returns the root value as minimum

DSA Java

while (current.left != null) { current = current.left; }

When to Use This Pattern

When you need the smallest value in a BST, look for a pattern that moves left until no more left child exists.

Common Mistakes

Mistake: Trying to find minimum by checking all nodes instead of just left children
Fix: Use the BST property and move only left until no left child

Mistake: Not handling empty tree and causing null pointer errors
Fix: Add a check for null root and throw an exception or handle gracefully

Summary

Finds the smallest value in a BST by moving left until no left child exists.

Use when you want the minimum element quickly in a BST.

The smallest value is always the leftmost node in a BST.

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.

2. Step 2: Locate minimum element

   The smallest value is found by moving left until no more left child exists.

3. Final Answer:

   At the leftmost node -> Option A

4. Quick Check:

   Minimum = leftmost node [OK]

Hint: Minimum is always the leftmost node in BST [OK]

Common Mistakes:

• Confusing minimum with root node
• Thinking minimum is rightmost node
• Assuming minimum can be any leaf

2. Which of the following Java code snippets correctly finds the minimum element in a BST node named root?

easy

A. while(root.right != null) { root = root.right; } return root.data;

B. while(root.left != null) { root = root.left; } return root.data;

C. if(root == null) return Integer.MAX_VALUE; return root.data;

D. return root.data;

Solution

1. Step 1: Check loop condition for minimum

   Minimum is found by moving left while left child exists.

2. Step 2: Verify code correctness

   while(root.left != null) { root = root.left; } return root.data; moves left until left child is null, then returns data.

3. Final Answer:

   while(root.left != null) { root = root.left; } return root.data; -> Option B

4. Quick Check:

   Loop left until null, then return [OK]

Hint: Traverse left children until none left [OK]

Common Mistakes:

• Traversing right child instead of left
• Returning root data without traversal
• Ignoring null root check

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

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; left = right = null; }
}

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

Node current = root;
while(current.left != null) {
  current = current.left;
}
System.out.println(current.data);

medium

A. 2

B. 7

C. 5

D. 10

Solution

1. Step 1: Trace the tree structure

   Root=10, left=5, right=15, left.left=2, left.right=7.

2. Step 2: Follow while loop to find minimum

   Start at 10, move left to 5, then left to 2, which has no left child.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Leftmost node data = 2 [OK]

Hint: Output is leftmost node's data after loop [OK]

Common Mistakes:

• Printing root data instead of leftmost
• Confusing left and right traversal
• Stopping loop too early

4. Identify the error in the following Java method to find the minimum element in a BST:

public int findMin(Node root) {
  if(root == null) return -1;
  while(root.right != null) {
    root = root.right;
  }
  return root.data;
}

medium

A. Method should be void, not int

B. Should return -1 only if root is leaf

C. Should check for root.data == null

D. Should traverse left child, not right child

Solution

1. Step 1: Analyze traversal direction

   Minimum element is found by moving left, not right.

2. Step 2: Identify correct traversal

   Loop should check root.left != null and move root = root.left.

3. Final Answer:

   Should traverse left child, not right child -> Option D

4. Quick Check:

   Minimum = leftmost node, so traverse left [OK]

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

Common Mistakes:

• Traversing right child instead of left
• Returning -1 incorrectly
• Checking data for null instead of node

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

public int findMinUnique(Node root) {
  Set<Integer> seen = new HashSet<>();
  int min = Integer.MAX_VALUE;
  while(root != null) {
    if(!seen.contains(root.data)) {
      min = Math.min(min, root.data);
      seen.add(root.data);
    }
    root = root.left;
  }
  return min;
}

What is the main issue with this method?

hard

A. It uses a HashSet unnecessarily for BST

B. It does not handle empty tree correctly

C. It only checks left children, missing other nodes

D. It returns max value instead of min

Solution

1. Step 1: Understand traversal logic

   Method only moves down left children, ignoring right subtree.

2. Step 2: Identify missed nodes

   Duplicates or unique values in right subtree are missed.

3. Step 3: Correct approach

   To find minimum unique, full tree traversal (e.g., inorder) is needed.

4. Final Answer:

   It only checks left children, missing other nodes -> Option C

5. Quick Check:

   Partial traversal misses right subtree [OK]

Hint: Traverse entire tree to find minimum unique value [OK]

Common Mistakes:

• Assuming left path covers all nodes
• Ignoring duplicates in right subtree
• Using HashSet without full traversal