Find min and max value in a BST

The problem, simply

You get a binary search tree (BST): at every spot, the left side is smaller and the right side is bigger. Give back the smallest number and the biggest number in the tree.

A story to remember it

Picture it

Examples

Way 1: the simple way

Visit every spot and remember the smallest and biggest number seen so far. This works for any tree, sorted or not.

1. Start with min as the biggest possible number and max as the smallest possible number.
2. Visit every spot. Update min and max.
3. Return both.

class Solution {
    private int min, max;

    public int[] findMinMax(TreeNode root) {
        if (root == null) return null;          // empty tree: no answer
        min = Integer.MAX_VALUE;
        max = Integer.MIN_VALUE;
        visit(root);
        return new int[] { min, max };
    }

    private void visit(TreeNode node) {
        if (node == null) return;
        min = Math.min(min, node.val);
        max = Math.max(max, node.val);
        visit(node.left);
        visit(node.right);
    }
}

How long it takes: every spot once, O(n). Extra room: the recursion goes as deep as the tree, O(h).

Way 2: the clever way

Use the slope of the playground.

1. For the smallest: start at the top, keep moving to left while there is a left child. Where you stop is the smallest.
2. For the biggest: start at the top, keep moving to right while there is a right child. Where you stop is the biggest.

Why it is right: everything on the left of a spot is smaller than it. So if a spot has a left child, it cannot be the smallest. The first spot with no left child has nothing smaller anywhere below it, and everything above it on the road was bigger.

class Solution {
    public int[] findMinMax(TreeNode root) {
        if (root == null) return null;          // empty tree: no answer
        TreeNode lo = root;
        while (lo.left != null) lo = lo.left;   // slide left
        TreeNode hi = root;
        while (hi.right != null) hi = hi.right; // climb right
        return new int[] { lo.val, hi.val };
    }
}

How long it takes: each road is at most the height of the tree, O(h). That is about log n for a balanced tree and n for a stick. Extra room: two fingers, O(1).

Watch out for

• An empty tree. Check for null before the loops, or you crash on lo.left.
• Using while (lo != null) and then reading lo.val. That loop runs off the tree. Test lo.left, not lo.
• For a normal binary tree (not a BST), this trick is wrong. You must use Way 1.

What interviewers ask next

• Find the second smallest. If the smallest has a right child, the answer is the leftmost spot of that right side. Otherwise it is the parent of the smallest. Or walk in sorted order and stop at the second number.
• Find the smallest number bigger than x (the ceiling). Walk down from the top. Each time you go left, remember the spot. The last remembered spot is the answer.
• Return the nodes instead of the values, so the caller can delete them. Same loops, return lo and hi.
• In Java's TreeMap, what are these? firstKey() and lastKey(). They walk the same roads.

Remember this

Grown-up words: the downhill left path is the left subtree, the end of the always-left road is the leftmost node (the minimum), the end of the always-right road is the rightmost node (the maximum), and the number of posts on the road is the height h.