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

function findMin(root) {
  let current = root;
  while (current.left !== null) {
    current = current.left;
  }
  return current.value;
}

This code finds the smallest value in a BST by moving left until no left child remains.

Execution Table

Step	Operation	Current Node Value	Left Child Exists?	Action	Visual State
1	Start at root	10	Yes	Move to left child	10 / \ 5 15
2	At node 5	5	Yes	Move to left child	10 / \ 5 15 / 2
3	At node 2	2	No	Stop, found minimum	10 / \ 5 15 / 2
Exit	Minimum found	2	N/A	Return 2	Final minimum node is 2

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we keep moving left to find the minimum?

Because in a BST, smaller values are always on the left. The execution_table shows moving left from 10 to 5, then 5 to 2, until no left child exists.

What if the tree has only one node?

The loop never runs because current.left is null at the start. The execution_table step 1 would show no left child, so the root is the minimum.

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 value. See step 3 in execution_table.

Visual Quiz - 3 Questions

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

A 2

B 5

C 10

D 15

💡 Hint

Check the 'current' variable in variable_tracker after step 2.

At which step does the algorithm stop moving left?

A Step 1

B Step 3

C Step 2

D Exit

💡 Hint

Look at the 'Left Child Exists?' column in execution_table.

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

A Null

B The right child's value

C The root node's value

D The smallest right child's leftmost node

💡 Hint

Refer to key_moments about single-node or no-left-child trees.

Concept Snapshot

BST Find Minimum Element:
- Start at root node
- Move left while left child exists
- When no left child, current node is minimum
- Return current node's value
- Works because BST left children are smaller

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. Continue moving left until you reach a node with no left child. That node holds the minimum value in the BST. This works because BSTs store smaller values on the left side. The code uses a loop to move left until current.left is null, then returns current.value. If the tree has only one node or the root has no left child, the root itself is the minimum. Stopping when current.left is null ensures we do not lose the node's value by moving beyond the smallest node.

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.

3. Final Answer:

   At the leftmost node -> Option C

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 JavaScript code snippets correctly finds the minimum element in a BST node structure where each node has left and value properties?

easy

A. function findMin(node) { while(node.left) { node = node.left; } return node.value; }

B. function findMin(node) { while(node.right) { node = node.right; } return node.value; }

C. function findMin(node) { return node.value; }

D. function findMin(node) { if(node.right) return findMin(node.right); else return node.value; }

Solution

1. Step 1: Check traversal direction

   Minimum is found by moving left, so loop should check node.left.

2. Step 2: Verify code correctness

   function findMin(node) { while(node.left) { node = node.left; } return node.value; } loops while node.left exists, then returns node.value, which is correct.

3. Final Answer:

   function findMin(node) { while(node.left) { node = node.left; } return node.value; } -> Option A

4. Quick Check:

   Traverse left until no left child [OK]

Hint: Loop left child nodes to find minimum [OK]

Common Mistakes:

• Looping right child instead of left
• Returning node.value without traversal
• Recursing on right child for minimum

3. Given the BST below and the function findMin that finds the minimum value, what will be the output?

const root = {
  value: 10,
  left: { value: 5, left: { value: 2, left: null, right: null }, right: null },
  right: { value: 15, left: null, right: null }
};

function findMin(node) {
  while(node.left) {
    node = node.left;
  }
  return node.value;
}

console.log(findMin(root));

medium

A. 15

B. 5

C. 10

D. 2

Solution

1. Step 1: Trace left children from root

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

2. Step 2: Return value of leftmost node

   Leftmost node is 2, so function returns 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Leftmost node value = 2 [OK]

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

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left and right child traversal
• Misreading tree structure

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

function findMin(node) {
  while(node.right) {
    node = node.right;
  }
  return node.value;
}

medium

A. It incorrectly traverses right child instead of left

B. It does not return the node value

C. It causes infinite loop

D. It throws syntax error

Solution

1. Step 1: Analyze traversal direction

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

2. Step 2: Identify correct traversal for minimum

   Minimum requires moving to node.left, so the bug is wrong direction.

3. Final Answer:

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

4. Quick Check:

   Minimum = leftmost, not rightmost [OK]

Hint: Minimum is leftmost, not rightmost traversal [OK]

Common Mistakes:

• Confusing left and right child traversal
• Assuming right child leads to minimum
• Not testing code with example trees

5. You want to find the minimum element in a BST that may be empty (null). Which of the following improved functions correctly handles this edge case and returns null if the tree is empty?

hard

A. function findMin(node) { while(node.left) { node = node.left; } return node.value; }

B. function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; }

C. function findMin(node) { if(node.left) return findMin(node.left); else return node.value; }

D. function findMin(node) { if(!node.left) return null; else return findMin(node.left); }

Solution

1. Step 1: Check for empty tree

   function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; } returns null immediately if node is null, handling empty tree.

2. Step 2: Traverse left children safely

   Then it loops left until no left child, returning minimum value correctly.

3. Final Answer:

   function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; } -> Option B

4. Quick Check:

   Check null first, then traverse left [OK]

Hint: Check for null before traversal to avoid errors [OK]

Common Mistakes:

• Not checking for null input
• Returning null incorrectly when node exists
• Recursing without base case for null