Find the minimum node in a binary search tree

You're in an IBM phone screen and the interviewer asks, "Given a binary search tree, how would you find its minimum value?" It sounds almost too simple, but that's the point. This problem tests whether you truly understand the BST ordering property and can translate that understanding into clean recursive code. It's the kind of question that separates candidates who memorize solutions from those who genuinely understand data structures.

TL;DR

In a binary search tree, the minimum value always lives at the leftmost node. Recursively traverse left until root.left is null, then return root.data. This runs in O(log n) time and O(log n) space for a balanced tree, since you only visit one node per level along the left spine. The problem is also commonly known as "Find Minimum in BST" on other platforms.

Why This Problem Matters

Finding the minimum in a BST is a foundational operation that shows up as a building block in more complex algorithms. BST deletion, for instance, requires finding the minimum of the right subtree to locate the in-order successor. Understanding how the BST property guides your traversal strategy will help you with problems like validating a BST, finding the kth smallest element, or implementing a priority queue backed by a BST.

Binary Search Trees: The Ordering Property

A binary search tree isn't just any binary tree. It enforces a strict ordering rule: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. This single property is what makes BSTs so powerful for search operations.

Notice how 4 and 6 are both in the left subtree of 10 (both smaller than 10), while 15 sits in the right subtree (larger than 10). This ordering holds at every node, not just the root.

The ordering property gives us a direct path to the minimum: keep going left. Every time you move to a left child, you're guaranteed to reach a smaller value. When there's no more left child to visit, you've found the smallest value in the entire tree.

Understanding the Problem

Let's look at the example from the problem:

Given: The root of a BST Task: Return the minimum data value Constraint: Better than linear time and space

In this tree, minData(root) should return 4. The values in sorted order would be [4, 5, 6, 10, 14, 15, 16], and 4 is the smallest.

Edge Cases to Consider

1. Single node: The root is the minimum
2. Left-skewed tree: Every node only has a left child, so the minimum is at the bottom
3. Root has no left child: The root itself is the minimum (all other values are in the right subtree)

A single-node tree is both root and minimum. The base case handles this immediately.

Solution Approach

The algorithm follows directly from the BST property. Ask yourself: "Where is the smallest value?" It must be in the left subtree, because the left subtree contains only values smaller than the current node. If there is no left subtree, the current node is the smallest.

This gives us a clean recursive structure:

• Base case: root.left is null, so return root.data
• Recursive case: call minData(root.left) to keep traversing left

Let's trace through our example tree:

The green path shows exactly where our algorithm goes: 10, then 5, then 4. At node 4, root.left is null, so we return 4.

Here's the recursion trace as a state diagram:

Each call checks if root.left exists. If it does, we recurse left. When it doesn't, we've found our answer.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public int minData(TreeNode root) {
    // Base case: no left child means this node holds the minimum
    if (root.left == null) {
      return root.data;
    }
    // Recursive case: the minimum is somewhere further left
    return minData(root.left);
  }
}

The beauty of this solution is how directly it maps to the BST property. There's no extra bookkeeping, no auxiliary data structures. You just follow the left pointers until they run out.

The Iterative Alternative

While the recursive solution is elegant, you can also solve this iteratively with O(1) space:

public int minData(TreeNode root) {
    while (root.left != null) {
        root = root.left;
    }
    return root.data;
}

The iterative version avoids the call stack overhead entirely. In an interview, mentioning both approaches and discussing the space tradeoff demonstrates solid engineering judgment.

Handling a Skewed Tree

What happens when the BST is completely left-skewed? Every node only has a left child, so our algorithm walks all the way down:

In this worst case, we visit all n nodes, making the time complexity O(n). This is worth mentioning in an interview because it shows you understand that BST performance depends on the tree's balance.

Complexity Analysis

Time Complexity: O(log n) average, O(n) worst case

We visit one node per level, following only left pointers. In a balanced BST, the height is log(n), so we visit at most log(n) nodes. In the worst case (completely left-skewed tree), the height equals n, and we visit every node.

Space Complexity: O(log n) average, O(n) worst case

The recursive call stack grows proportionally to the number of recursive calls, which equals the height of the left spine. For a balanced tree, that's O(log n). For a skewed tree, it's O(n). The iterative approach eliminates this space cost entirely.

Common Pitfalls

1. Checking root == null instead of root.left == null: The problem guarantees at least one node, so the root is never null. The correct base case checks if the left child is null, not the root itself.

2. Traversing the entire tree: Some candidates try to visit every node and track a running minimum. This works but ignores the BST property and runs in O(n) time instead of O(log n).

3. Confusing BST with general binary tree: In a general binary tree, you'd need to check every node. The BST ordering property is what allows us to only follow left pointers.

Interview Tips

When solving this in an interview:

1. State the BST property explicitly: "In a BST, all left subtree values are smaller than the current node." This signals you understand the fundamentals.

2. Start with the recursive approach: It's cleaner and maps directly to the problem structure.

3. Mention the iterative alternative: After presenting the recursive solution, note that an iterative version exists with O(1) space.

4. Discuss the balanced vs. skewed distinction: Explaining that O(log n) assumes a balanced tree shows depth of understanding.

5. Connect to related operations: "This same technique is used in BST deletion to find the in-order successor."

Key Takeaways

• The BST ordering property guarantees the minimum value is at the leftmost node. Always follow left pointers until root.left is null.
• The recursive solution is two lines of logic: a base case check and a recursive call. Clean, readable code wins interviews.
• Time and space are both O(log n) for balanced trees, degrading to O(n) for skewed trees. The iterative approach achieves O(1) space.
• This algorithm is a subroutine of BST deletion (finding the in-order successor), so mastering it pays dividends on harder problems.
• Finding the maximum is the mirror operation: traverse right instead of left.

Solutions in Other Languages

Python

class Solution:
    def min_data(self, root: TreeNode) -> int:
        if root.left is None:
            return root.data
        return self.min_data(root.left)

JavaScript

class Solution {
  minData(root) {
    if (root.left === null) {
      return root.data;
    }
    return this.minData(root.left);
  }
}

TypeScript

class Solution {
  minData(root: TreeNode): number {
    if (root.left === null) {
      return root.data;
    }
    return this.minData(root.left);
  }
}

C++

class Solution {
public:
  int minData(TreeNode *root) {
    if (root->left == nullptr) {
      return root->data;
    }
    return minData(root->left);
  }
};

Scala

class Solution {
  def minData(root: TreeNode): Int = {
    if (root.left == null) {
      root.data
    } else {
      minData(root.left)
    }
  }
}

Kotlin

class Solution {
    fun minData(root: TreeNode): Int {
        if (root.left == null) {
            return root.data
        }
        return minData(root.left!!)
    }
}

Swift

class Solution {
    func minData(_ root: TreeNode?) -> Int {
        if root!.left == nil {
            return root!.data
        }
        return minData(root!.left)
    }
}

Ruby

class Solution
  def min_data(root)
    return root.data if root.left.nil?
    min_data(root.left)
  end
end

Rust

impl Solution {
    pub fn min_data(&self, root: Option<Box<TreeNode>>) -> i32 {
        let node = root.unwrap();
        if node.left.is_none() {
            return node.data;
        }
        self.min_data(node.left)
    }
}

C#

public class Solution {
    public int minData(TreeNode? root) {
        if (root.left == null) {
            return root.data;
        }
        return minData(root.left);
    }
}

Dart

class Solution {
  int minData(TreeNode? root) {
    if (root!.left == null) {
      return root.data;
    }
    return minData(root.left);
  }
}

PHP

class Solution {
    public function minData(?TreeNode $root): int {
        if ($root->left === null) {
            return $root->data;
        }
        return $this->minData($root->left);
    }
}

Practice Makes Perfect

Once you're comfortable finding the minimum in a BST, try these related problems to deepen your understanding:

• Recursively find the maximum node of a binary tree
• Find the kth smallest element in a BST
• Validate a binary search tree
• Delete a node from a BST (which uses the minimum-finding technique as a subroutine)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Whether you're just starting out or sharpening your skills for a FAANG interview, building a strong foundation with problems like this will set you apart.