Find the Minimum Value in a BST

Given the root of a binary search tree, return its smallest value, or an empty OptionalInt if the tree is empty.

Example

Text

Values inserted in this order: 6, 4, 9, 2, 5, 12
Output: 2

graph TB
    a["6"] --> b["4"]
    a --> c["9"]
    b --> d["2 (minimum)"]
    b --> e["5"]
    c --> f["12"]
    style d stroke-width:3px

Brute force: visit every node

Ignore the BST ordering: the minimum of a tree is the smallest of the root's value, the minimum of the left subtree, and the minimum of the right subtree. This works for any binary tree.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. The fields are mutable, so no wrapper type is needed. OptionalInt is a container that holds either one int or nothing, so a method can report "no answer" without returning null.

Java

import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static OptionalInt findMin(TreeNode root) {
        if (root == null) return OptionalInt.empty();
        int min = root.val;
        OptionalInt left = findMin(root.left);
        OptionalInt right = findMin(root.right);
        if (left.isPresent()) min = Math.min(min, left.getAsInt());
        if (right.isPresent()) min = Math.min(min, right.getAsInt());
        return OptionalInt.of(min);
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 12);
        System.out.println(findMin(root) + " " + findMin(null));
    }
}

Output

OptionalInt[2] OptionalInt.empty

Time: O(n): every node is visited. Space: O(h) for the recursion.

Optimal: keep going left

In a BST, every value in a node's left subtree is smaller than the node. So the minimum is the node you reach by following left links from the root until there is no left child.

Walkthrough: 6 has a left child, 4 has a left child, 2 has no left child, so return 2.

Java

import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static OptionalInt findMin(TreeNode root) {
        if (root == null) return OptionalInt.empty();
        TreeNode node = root;
        while (node.left != null) {
            node = node.left;
        }
        return OptionalInt.of(node.val);
    }

    static OptionalInt findMax(TreeNode root) {
        if (root == null) return OptionalInt.empty();
        TreeNode node = root;
        while (node.right != null) {
            node = node.right;
        }
        return OptionalInt.of(node.val);
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 12);
        System.out.println(findMin(root) + " " + findMin(null));
        System.out.println(findMax(root));
        System.out.println(findMin(fromValues(10, 20, 30))); // no left children: the root is the minimum
    }
}

Output

OptionalInt[2] OptionalInt.empty
OptionalInt[12]
OptionalInt[10]

Time: O(h): O(log n) for a balanced tree, O(n) for a degenerate one. Space: O(1).

The root == null check returns an empty result right away for an empty tree. The maximum is found the same way, following right links.

Edge cases

Empty tree: OptionalInt.empty().
Root without a left child: the root is the minimum.
Duplicates: this course inserts equal values to the right, so the leftmost node is still a minimum.