BST Find Minimum Element in DSA Typescript

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 youngest child is always the leftmost branch; to find the youngest, you keep moving left until you can't go further.

      10
     /  \
    5    15
   / 
  2  
 / 
1
↑

Dry Run Walkthrough

Input: BST with nodes 10, 5, 15, 2, 1; find minimum element

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

Step 1: Start at root node 10

10 -> left: 5 -> left: 2 -> left: 1 -> null
↑ at 10

Why: We begin at the root to find the minimum

Step 2: Move left from 10 to 5

10 -> [curr->5] -> 15
5 -> left: 2 -> left: 1 -> null
↑ at 5

Why: Minimum is in left subtree, so move left

Step 3: Move left from 5 to 2

5 -> [curr->2] -> left: 1 -> null
↑ at 2

Why: Continue moving left to find smaller values

Step 4: Move left from 2 to 1

2 -> [curr->1] -> null
↑ at 1

Why: No more left child, so 1 is minimum

Result:

1 -> null
Minimum element found: 1

Annotated Code

DSA Typescript

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
  }
}

function findMin(root: TreeNode | null): number | null {
  if (root === null) return null;
  let curr = root;
  while (curr.left !== null) {
    curr = curr.left; // advance curr to left child to find smaller value
  }
  return curr.val; // curr is now the smallest element
}

// Driver code to build the BST and find minimum
const root = new TreeNode(10,
  new TreeNode(5,
    new TreeNode(2,
      new TreeNode(1),
      null
    ),
    null
  ),
  new TreeNode(15)
);

const minVal = findMin(root);
console.log(minVal !== null ? `${minVal} -> null` : "Tree is empty");

while (curr.left !== null) {

keep moving left to find smaller values

curr = curr.left; // advance curr to left child to find smaller value

advance curr pointer to left child

return curr.val; // curr is now the smallest element

return the value of the leftmost node

Output

1 -> null

Complexity Analysis

Time: O(h) because we traverse down the height of the tree following left children

Space: O(1) because we only use a pointer variable without extra data structures

vs Alternative: Compared to traversing all nodes (O(n)), this approach is faster as it only goes down the left edge

Edge Cases

Empty tree (root is null)

Returns null indicating no minimum element

DSA Typescript

if (root === null) return null;

Tree with only one node

Returns the value of the single node as minimum

DSA Typescript

while (curr.left !== null) {

All nodes only have right children (no left children)

Returns root value as minimum since no left child exists

DSA Typescript

while (curr.left !== null) {

When to Use This Pattern

When you need the smallest element in a BST, look for the leftmost node by moving left until no more left child exists.

Common Mistakes

Mistake: Trying to find minimum by traversing the entire tree instead of just left children
Fix: Only move left from the root until no left child exists to find minimum efficiently

Mistake: Not handling empty tree (null root) case
Fix: Add a check at start to return null if root is null

Summary

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

Use when you want to quickly find the minimum element in a BST.

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

Practice

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

easy

A. At any leaf node

B. At the rightmost node

C. At the root node

D. At the leftmost 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 D

4. Quick Check:

   Minimum element = leftmost node [OK]

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

Common Mistakes:

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

2. Which TypeScript code snippet correctly finds the minimum element in a BST node?

easy

A. while (node.right !== null) { node = node.right; } return node.value;

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

C. if (node.value < min) min = node.value; return min;

D. return Math.min(node.value, node.left.value);

Solution

1. Step 1: Check traversal direction for minimum

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

2. Step 2: Verify code correctness

   while (node.left !== null) { node = node.left; } return node.value; correctly loops left and returns node value; others are incorrect or incomplete.

3. Final Answer:

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

4. Quick Check:

   Traverse left to find minimum [OK]

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

Common Mistakes:

• Traversing right child instead of left
• Using Math.min without checking null nodes
• Not looping until leftmost node

3. What will be the output of the following TypeScript code?

class Node {
  constructor(public value: number, public left: Node | null = null, public right: Node | null = null) {}
}

const root = new Node(10, new Node(5, new Node(2), new Node(7)), new Node(15));

function findMin(node: Node): number {
  while (node.left !== null) {
    node = node.left;
  }
  return node.value;
}

console.log(findMin(root));

medium

A. 7

B. 5

C. 2

D. 10

Solution

1. Step 1: Analyze BST structure

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

2. Step 2: Trace findMin function

   Function moves left from 10 to 5, then to 2, which has no left child, so returns 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Minimum value in BST = 2 [OK]

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

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left and right child nodes
• Stopping traversal too early

4. Identify the bug in this TypeScript function to find the minimum element in a BST:

function findMin(node: Node | null): number {
  if (node === null) return -1;
  while (node.right !== null) {
    node = node.right;
  }
  return node.value;
}

medium

A. Traverses right child instead of left child

B. Returns -1 for empty tree, should throw error

C. Does not check if node is null before accessing value

D. Returns node.value before loop ends

Solution

1. Step 1: Check traversal direction

   Minimum element requires moving left, but code moves right.

2. Step 2: Identify correct fix

   Change 'node.right' to 'node.left' in the while loop to find minimum.

3. Final Answer:

   Traverses right child instead of left child -> Option A

4. Quick Check:

   Minimum found by left traversal, not right [OK]

Hint: Minimum is leftmost, so traverse left child nodes [OK]

Common Mistakes:

• Using right child traversal for minimum
• Ignoring null checks before access
• Returning default -1 instead of handling empty tree

5. Given a BST where some nodes have duplicate values, how would you modify the findMin function to return the smallest unique value?

hard

A. Traverse entire tree and collect all values, then find minimum

B. Return the first leftmost node value without checking duplicates

C. Traverse leftmost nodes and skip duplicates by checking parent values

D. Use rightmost node value as minimum to avoid duplicates

Solution

1. Step 1: Understand duplicates in BST

   Duplicates can appear on left or right; leftmost node may not be unique minimum.

2. Step 2: Modify approach to find unique minimum

   Traverse entire tree to collect all values, then find the smallest unique value.

3. Final Answer:

   Traverse entire tree and collect all values, then find minimum -> Option A

4. Quick Check:

   Full traversal needed for unique minimum [OK]

Hint: Traverse all nodes to find unique minimum value [OK]

Common Mistakes:

• Assuming leftmost node is always unique minimum
• Ignoring duplicates in traversal
• Using rightmost node as minimum