BST Find Minimum Element in DSA C++ - Execution Trace

Concept Flow - BST Find Minimum Element

Start at root

↓

Check if current.left exists?

No→Current node is minimum

Yes↓

Move current to current.left

↩Back to check

Start at the root node and keep moving left until no left child exists. The last node reached is the minimum.

Execution Sample

DSA C++

Node* findMin(Node* root) {
  Node* current = root;
  while (current != nullptr && current->left != nullptr) {
    current = current->left;
  }
  return current;
}

This code finds the minimum element in a BST by moving left until no left child exists.

Execution Table

Step	Operation	Current Node	Pointer Changes	Visual State
1	Start at root	50	current = root (50)	50 / \ 30 70 / \ \ 20 40 80
2	Check if current.left exists	50	Yes, move current to 30	50 / \ 30 70 / \ \ 20 40 80
3	Check if current.left exists	30	Yes, move current to 20	50 / \ 30 70 / \ \ 20 40 80
4	Check if current.left exists	20	No left child, stop	50 / \ 30 70 / \ \ 20 40 80
5	Return current as minimum	20	Return node with value 20	Minimum element found: 20

💡 Stopped when current node (20) has no left child

Variable Tracker

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

Key Moments - 3 Insights

Why do we keep moving left to find the minimum?

In a BST, smaller values are always in the left subtree. So moving left leads to the smallest value. See execution_table steps 2 and 3 where current moves left.

What if the tree is empty (root is nullptr)?

The code checks if current is nullptr before accessing left. If root is nullptr, current is nullptr and the loop doesn't run, returning nullptr immediately.

Why do we stop when current->left is nullptr, not when current is nullptr?

Because current itself is a valid node holding the minimum value. If current were nullptr, it means we went past the leaf. See execution_table step 4 where current is 20 and has no left child.

Visual Quiz - 3 Questions

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

A 20

B 50

C 30

D 40

💡 Hint

Check the 'current' column in execution_table row for step 3.

At which step does the condition 'current->left != nullptr' become false?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table for step 4.

If the root node had no left child, what would be the minimum element?

A nullptr

B The right child of root

C The root node itself

D The leftmost leaf

💡 Hint

Refer to the concept_flow and execution_table step 1 and 4 where no left child means current node is minimum.

Concept Snapshot

BST Find Minimum Element:
- Start at root node
- Move left child repeatedly
- Stop when no left child
- Current node is minimum
- Returns pointer to minimum node

Full Transcript

To find the minimum element in a Binary Search Tree (BST), start at the root node. Because smaller values are always on the left, keep moving to the left child node until you reach a node that has no left child. That node holds the minimum value. The code uses a pointer 'current' starting at root and moves left while current->left is not null. When current->left is null, current points to the minimum node. If the tree is empty, the function returns nullptr immediately. This process ensures the smallest element is found efficiently.

Practice

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

easy

A. At any leaf node

B. At the leftmost node

C. At the root node

D. At the rightmost 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 left until no more left child exists.

3. Final Answer:

   At the leftmost node -> Option B

4. Quick Check:

   Minimum = leftmost node [OK]

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

Common Mistakes:

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

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

easy

A. while(root->left != nullptr) root = root->left; return root->data;

B. while(root->right != nullptr) root = root->right; return root->data;

C. if(root == nullptr) return INT_MAX; return root->data;

D. return root->data;

Solution

1. Step 1: Check traversal direction

   Minimum is found by moving left until no left child exists.

2. Step 2: Verify code correctness

   while(root->left != nullptr) root = root->left; return root->data; loops left correctly and returns the leftmost node's data.

3. Final Answer:

   while(root->left != nullptr) root = root->left; return root->data; -> Option A

4. Quick Check:

   Traverse left to find minimum [OK]

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

Common Mistakes:

• Looping right child instead of left
• Returning root data without traversal
• Not checking for nullptr before access

3. What is the output of the following C++ code snippet?

struct Node {
  int data;
  Node* left;
  Node* right;
};

Node* root = new Node{10, nullptr, nullptr};
root->left = new Node{5, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};
root->left->left = new Node{2, nullptr, nullptr};

Node* temp = root;
while(temp->left != nullptr) {
  temp = temp->left;
}
std::cout << temp->data << std::endl;

medium

A. 10

B. 5

C. 2

D. 15

Solution

1. Step 1: Trace the tree structure

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

2. Step 2: Follow the loop to find minimum

   Loop moves from 10 to 5, then to 2, which has no left child.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Leftmost node data = 2 [OK]

Hint: Follow left pointers until null to find minimum [OK]

Common Mistakes:

• Stopping at root or first left child
• Confusing right child as minimum
• Not tracing loop fully

4. Identify the error in the following C++ function to find the minimum element in a BST:

int findMin(Node* root) {
  if(root == nullptr) return -1;
  while(root->right != nullptr) {
    root = root->right;
  }
  return root->data;
}

medium

A. Loops on right child instead of left child

B. Returns -1 when root is nullptr

C. Returns root->data without checking nullptr

D. Function return type should be Node*

Solution

1. Step 1: Analyze loop direction

   Minimum element is found by moving left, not right.

2. Step 2: Identify incorrect traversal

   The code loops on root->right, which finds maximum, not minimum.

3. Final Answer:

   Loops on right child instead of left child -> Option A

4. Quick Check:

   Minimum requires left traversal [OK]

Hint: Minimum is leftmost, not rightmost [OK]

Common Mistakes:

• Using right child loop for minimum
• Ignoring nullptr checks
• Confusing min and max logic

5. Given a BST where some nodes have only right children, how would you modify the standard minimum element search to handle this edge case correctly?

hard

A. Return root data immediately if left child is nullptr

B. Traverse right child until nullptr to find minimum

C. Use recursion to check both left and right children

D. Traverse left child until nullptr; if none, root is minimum

Solution

1. Step 1: Understand edge case

   If no left child exists, root itself is minimum.

2. Step 2: Modify search logic

   Traverse left until nullptr; if none found, root is minimum.

3. Final Answer:

   Traverse left child until nullptr; if none, root is minimum -> Option D

4. Quick Check:

   Minimum = leftmost or root if no left child [OK]

Hint: If no left child, root is minimum [OK]

Common Mistakes:

• Assuming minimum always has left child
• Traversing right child for minimum
• Not handling single-child nodes