Topics › Binary Search Trees › Concepts

Find Min/Max in BST

Easy TUF ID 2398 A2Z

Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given the root of a binary search tree, return its smallest and largest keys as {min, max}. If the tree is empty, return {-1, -1}, which is the convention used by the common judge versions of this problem (they ask for the minimum or the maximum separately and return -1 for an empty tree).

The BST property holds: for every node, all keys in its left subtree are smaller than its key, and all keys in its right subtree are larger.

Constraints: up to 10^5 nodes; keys fit in an int.

Example 1

          5
        /   \
       3     8
      / \   / \
     1   4 7   9          answer = {1, 9}

The minimum is reached by always going left from the root, the maximum by always going right.

Example 2

       5
      / \
     3   8                answer = {3, 8}
      \
       4

The minimum 3 is not a leaf: it has a right child 4, which is larger than 3, so it does not change the answer.

Approach 1: Brute force, visit every node

Intuition. If we forget that the tree is a BST, finding the extremes means looking at every key once and keeping a running minimum and maximum, as for an unsorted array. Any traversal order works; here an explicit stack does a preorder walk. This is correct for any binary tree, and that generality is its weakness: it ignores the one property that makes the problem easy.

Algorithm.

1. If the root is null, return {-1, -1}.
2. Start with min = Integer.MAX_VALUE and max = Integer.MIN_VALUE, and push the root.
3. While the stack is not empty, pop a node, update min and max with its key, and push its non-null children.
4. Return {min, max}.

static int[] bruteForce(TreeNode root) {
    if (root == null) return new int[]{-1, -1};
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        min = Math.min(min, node.val);
        max = Math.max(max, node.val);
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }
    return new int[]{min, max};
}

Complexity. Time O(n): every node is pushed and popped once. Space O(h): after each pop the left child is expanded next, so the stack holds at most one pending right child per level.

Approach 2: Recursive walk down the edges

Intuition. Where can the minimum be? Look at the root. If it has a left subtree, every key there is smaller than the root, and every key in the right subtree is larger than the root, so the minimum must be in the left subtree. If the root has no left subtree, then the root is smaller than everything in its right subtree, so the root itself is the minimum. Apply the same reasoning to the left child, and so on: the minimum is the node reached by going left until there is no left child. By the mirror argument, the maximum is reached by going right until there is no right child.

This is the tree version of “the first element of a sorted array”. In the inorder sequence (which is sorted for a BST), the leftmost node comes first and the rightmost node comes last.

Algorithm.

1. If the root is null, return {-1, -1}.
2. leftmost(node): if node.left is null, return node.val; otherwise recurse on node.left.
3. rightmost(node): the mirror image using node.right.
4. Return {leftmost(root), rightmost(root)}.

static int[] recursive(TreeNode root) {
    if (root == null) return new int[]{-1, -1};
    return new int[]{leftmost(root), rightmost(root)};
}

static int leftmost(TreeNode node) {
    return node.left == null ? node.val : leftmost(node.left);
}

static int rightmost(TreeNode node) {
    return node.right == null ? node.val : rightmost(node.right);
}

Complexity. Time O(h): each walk visits one node per level of one edge. Space O(h) for the recursion stack.

Approach 3: Optimal, two loops

Intuition. Both helper functions in Approach 2 are tail-recursive: each call just hands its result back. Replacing the calls with a pointer that moves down the edge gives the same walk with constant extra space.

Algorithm.

1. If the root is null, return {-1, -1}.
2. Set lo = hi = root.
3. While lo.left exists, move lo left. While hi.right exists, move hi right.
4. Return {lo.val, hi.val}.

static int[] optimal(TreeNode root) {
    if (root == null) return new int[]{-1, -1};
    TreeNode lo = root, hi = root;
    while (lo.left != null) lo = lo.left;            // smaller keys are always to the left
    while (hi.right != null) hi = hi.right;          // larger keys are always to the right
    return new int[]{lo.val, hi.val};
}

Dry run on Example 2:

Note that the min walk stops at 3 even though 3 has a right child. The walk only ever follows left links.

Complexity. Time O(h), Space O(1). For a balanced tree that is O(log n); for a chain it degrades to O(n), no worse than the brute force.

Edge cases and pitfalls

• Empty tree. Check for null before reading root.left; all three methods return {-1, -1}. If the keys can be negative, -1 is ambiguous, and a real API should return null, an Optional, or throw instead.
• Single node. It is both the minimum and the maximum: {10} gives {10, 10}.
• The minimum is not necessarily a leaf. It can have a right child (Example 2). A walk that “goes left, or right if there is no left, until reaching a leaf” ends at 4 and returns the wrong answer. Only follow left links.
• The root can be an extreme. In a right-leaning chain 1 → 2 → 3 the root is the minimum, because it has no left child. The loop simply runs zero times.
• Extreme values. The brute force starts its running minimum at Integer.MAX_VALUE; a tree containing Integer.MAX_VALUE still works because Math.min keeps equal values correctly. The edge walks do no arithmetic at all, so they cannot overflow.
• Not a BST. The O(h) methods are only correct when the BST property holds; for a general binary tree, Approach 1 is the right tool.

Related problems

• Introduction to BST explains why smaller keys are always to the left.
• Search in a Binary Search Tree uses the same one-path walk to find a specific key.
• Delete a node in BST needs the minimum of a right subtree, the inorder successor, when a node has two children.
• Inorder Successor/Predecessor in BST generalises “go left as far as possible” to the next key after any node.
• Kth Smallest and Largest element in BST is this problem with k = 1 generalised to any k.