BST Find Minimum Element in DSA C# - 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

↩Back to check left child

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

Execution Sample

DSA C#

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	20	Yes	current = 20	20 / \ 10 30
2	Move left	10	Yes	current = 10	20 / \ 10 30 / 5
3	Move left	5	No	current = 5	20 / \ 10 30 / 5
4	Return current	5	No	Return node 5	Minimum found: 5

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we stop when current.Left is null and not when current itself is null?

Because current is always a valid node; we stop when there is no left child to move to, meaning current is the smallest node (see execution_table step 3 and 4).

What if the BST has only one node?

The root node has no left child, so the loop never runs and the root is returned immediately as minimum (see execution_table step 1).

Why do we keep moving left instead of right?

In a BST, smaller values are always in the left subtree, so the minimum is found by going left until no more left child exists (see concept_flow).

Visual Quiz - 3 Questions

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

A 10

B 5

C 20

D 30

💡 Hint

Check the 'Pointer Changes' and 'Current Node' columns in execution_table row for step 2.

At which step does the loop stop because there is no left child?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

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

If the BST had no left children at all, what would be the minimum node returned?

A The root node

B The rightmost node

C Null

D The leftmost leaf

💡 Hint

Refer to key_moments about the single node or no left child case.

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 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 loop to move left until no left child is found, then returns that node. If the tree has only one node, that node is the minimum. This method ensures the smallest value is found efficiently by following the left pointers.

Practice

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

easy

A. At the rightmost node

B. At the root node

C. At the leftmost 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 going as far left as possible from the root.

3. Final Answer:

   At the leftmost node -> Option C

4. Quick Check:

   Minimum element = leftmost node [OK]

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

Common Mistakes:

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

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

easy

A. while (root.Left != null) { root = root.Left; } return root.Value;

B. while (root.Right != null) { root = root.Right; } return root.Value;

C. return root.Value;

D. while (root != null) { root = root.Left; } return root.Value;

Solution

1. Step 1: Check loop condition for minimum

   Minimum is found by moving left while left child exists.

2. Step 2: Validate code correctness

   while (root.Left != null) { root = root.Left; } return root.Value; moves left until null, then returns last node's value correctly.

3. Final Answer:

   while (root.Left != null) { root = root.Left; } return root.Value; -> Option A

4. Quick Check:

   Traverse left until null, then return value [OK]

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

Common Mistakes:

• Traversing right child instead of left
• Returning root value without traversal
• Looping until root is null causing error

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

class Node {
  public int Value;
  public Node Left, Right;
  public Node(int val) { Value = val; }
}

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;
}
Console.WriteLine(current.Value);

medium

A. 7

B. 2

C. 5

D. 10

Solution

1. Step 1: Trace the tree structure

   Root is 10, left child 5, left-left child 2, left-right child 7.

2. Step 2: Follow the loop to find minimum

   Loop moves from 10 to 5, then to 2 (leftmost node). 2 has no left child, loop stops.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Leftmost node value is printed after loop [OK]

Common Mistakes:

• Printing root value instead of leftmost
• Confusing left-right child as minimum
• Stopping loop too early

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

int FindMin(Node root) {
  while (root != null) {
    root = root.Left;
  }
  return root.Value;
}

medium

A. The method should check root.Right instead of root.Left

B. The method should return root.Left.Value instead of root.Value

C. The method should use recursion instead of a loop

D. The loop condition should be root.Left != null, not root != null

Solution

1. Step 1: Analyze loop condition

   Loop runs while root is not null, but root becomes null after last left move.

2. Step 2: Identify cause of error

   After loop, root is null, so accessing root.Value causes error. Condition should be root.Left != null to stop at last node.

3. Final Answer:

   The loop condition should be root.Left != null, not root != null -> Option D

4. Quick Check:

   Stop before null to access valid node [OK]

Hint: Loop until root.Left is null, not root itself [OK]

Common Mistakes:

• Looping until root is null causing null reference
• Returning value after root becomes null
• Checking right child instead of left

5. Given a BST where some nodes have duplicate values, which approach correctly finds the minimum element considering duplicates are allowed only on the right subtree?

class Node {
  public int Value;
  public Node Left, Right;
  public Node(int val) { Value = val; }
}

// Duplicates go to right subtree

Which code snippet correctly finds the minimum element?

hard

A. while (root.Left != null) { root = root.Left; } return root.Value;

B. while (root.Right != null) { root = root.Right; } return root.Value;

C. return root.Value; // root is minimum due to duplicates on right

D. while (root.Left != null && root.Left.Value < root.Value) { root = root.Left; } return root.Value;

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates go to right subtree, so minimum is still in leftmost path.

2. Step 2: Confirm traversal for minimum

   Traverse left child nodes until no more left child exists to find minimum.

3. Final Answer:

   while (root.Left != null) { root = root.Left; } return root.Value; -> Option A

4. Quick Check:

   Minimum is leftmost node even with duplicates on right [OK]

Hint: Duplicates on right don't affect leftmost minimum [OK]

Common Mistakes:

• Checking right subtree for minimum
• Assuming root is minimum without traversal
• Adding extra conditions unnecessarily