BST Find Minimum Element in DSA Javascript

Mental Model

In a Binary Search Tree, the smallest value is always found by going left until no more left child exists.

Analogy: Imagine a family tree where the oldest ancestor is always on the far left branch; to find the oldest, you keep moving left until you can't go further.

      10
     /  \
    5    15
   / 
  2  
 ↑ (start here at root)

Dry Run Walkthrough

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

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

Step 1: Start at root node with value 10

10 -> 5 -> 15 -> 2, current at 10 ↑

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

Step 2: Move left from 10 to node 5

10 -> [curr->5] -> 15 -> 2

Why: Minimum is always in the left subtree, so we go left

Step 3: Move left from 5 to node 2

10 -> 5 -> 15 -> [curr->2]

Why: Keep moving left to find smaller values

Step 4: Node 2 has no left child, stop here

10 -> 5 -> 15 -> 2 [curr], left child is null

Why: No more left nodes means current node is minimum

Result:

Minimum element found: 2
BST structure: 10 -> 5 -> 15 -> 2

Annotated Code

DSA Javascript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(value) {
    const newNode = new Node(value);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let curr = this.root;
    while (true) {
      if (value < curr.value) {
        if (!curr.left) {
          curr.left = newNode;
          return;
        }
        curr = curr.left; // advance left
      } else {
        if (!curr.right) {
          curr.right = newNode;
          return;
        }
        curr = curr.right; // advance right
      }
    }
  }

  findMin() {
    if (!this.root) return null; // empty tree
    let curr = this.root;
    while (curr.left) {
      curr = curr.left; // move left to find min
    }
    return curr.value; // leftmost node value
  }
}

// Driver code
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
console.log("Minimum element found:", bst.findMin());

while (curr.left) {

keep moving left to find the smallest value

curr = curr.left;

advance current node to its left child

return curr.value;

return the value of the leftmost node as minimum

Output

Minimum element found: 2

Complexity Analysis

Time: O(h) where h is the height of the tree because we move down only the left children

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 because BST structure guides directly to minimum

Edge Cases

Empty tree

Returns null since there is no minimum

DSA Javascript

if (!this.root) return null;

Tree with only one node

Returns the root value as minimum

DSA Javascript

while (curr.left) { ... } returns root value if no left child

All nodes only on right side (no left children)

Returns root value as minimum since no left child exists

DSA Javascript

while (curr.left) { ... } stops immediately if no left child

When to Use This Pattern

When asked to find the smallest element in a BST, look for the leftmost node by following left children until none remain.

Common Mistakes

Mistake: Trying to check right children or scanning entire tree for minimum
Fix: Only follow left children from root until left child is null

Mistake: Not handling empty tree and returning undefined or error
Fix: Add a check for empty root and return null

Summary

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

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

The smallest element is always the leftmost node in the BST.

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