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.