BST Find Minimum Element in DSA Java - Execution Trace

Concept Flow - BST Find Minimum Element

Start at root node

↓

Check if left child exists?

No→Current node is minimum

Yes↓

Move to left child

↓

Repeat check

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

Execution Sample

DSA Java

Node findMin(Node root) {
  Node current = root;
  while (current.left != null) {
    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	50	Yes	current = 50	50 / \ 30 70
2	Move left	30	Yes	current = 30	50 / \ 30 70 / 20
3	Move left	20	No	current = 20	50 / \ 30 70 / 20
4	Return current	20	No	Return node 20	Minimum found: 20

💡 Left child of current node is null, so current node is minimum.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	root (50)	50	30	20	20

Key Moments - 3 Insights

Why do we keep moving left to find the minimum?

Because in a BST, smaller values are always in the left subtree. The execution_table rows 2 and 3 show moving left until no left child exists.

What if the root has no left child?

Then the root itself is the minimum. This would be the case if 'Left Child Exists?' was No in execution_table row 1.

Why do we stop when current.left is null, not when current is null?

Stopping at current.left == null means current is the smallest node. If we went further, current would become null and lose the node reference. See execution_table row 3 and 4.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'current' at Step 2?

A 50

B 20

C 30

D 70

💡 Hint

Check the 'Current Node' column at Step 2 in the execution_table.

At which step does the algorithm find that the left child does not exist?

A Step 2

B Step 3

C Step 1

D Step 4

💡 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 node returned?

A The root node itself

B The right child of root

C Null

D The leftmost leaf

💡 Hint

Refer to key_moments about what happens if root has no left child.

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 the pointer to the left child and repeat. If no left child exists, the current node is the minimum. This works because in BSTs, smaller values are always on the left. The code uses a while loop to move left until no left child is found, then returns that node. The execution table shows the pointer moving from 50 to 30 to 20, stopping when 20 has no left child. This method ensures the smallest value is found efficiently.

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