Check if a tree is a BST or not

The problem, simply

You get a binary tree. Say true if it is a binary search tree (BST), and false if not.

A BST has one rule, and it is stronger than it looks: for every spot, every number anywhere on its left side is smaller than it, and every number anywhere on its right side is bigger. Checking only a spot and its two children is not enough.

A story to remember it

Picture it

Examples

Way 1: the simple way

For every spot, look at its whole left side and find the biggest number there. Look at its whole right side and find the smallest. The spot must sit strictly between them.

1. If the biggest number on the left is not smaller than the spot, say false.
2. If the smallest number on the right is not bigger than the spot, say false.
3. Do the same for every spot below.

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        if (root.left != null && maxOf(root.left) >= root.val) return false;
        if (root.right != null && minOf(root.right) <= root.val) return false;
        return isValidBST(root.left) && isValidBST(root.right);
    }

    // the biggest number anywhere in this part of the tree
    private int maxOf(TreeNode n) {
        int best = n.val;
        if (n.left != null) best = Math.max(best, maxOf(n.left));
        if (n.right != null) best = Math.max(best, maxOf(n.right));
        return best;
    }

    private int minOf(TreeNode n) {
        int best = n.val;
        if (n.left != null) best = Math.min(best, minOf(n.left));
        if (n.right != null) best = Math.min(best, minOf(n.right));
        return best;
    }
}

How long it takes: every spot scans everything below it. For a stick shaped tree that is n + (n - 1) + ... + 1, so O(n^2). Extra room: the recursion depth, O(h).

Way 2: the clever way

Give every spot its rule card: a window (low, high) that it must sit strictly inside.

1. The top gets the window (no limit, no limit).
2. When you step to the left child, the window's high end becomes the parent's value. The low end stays.
3. When you step to the right child, the window's low end becomes the parent's value. The high end stays.
4. If any spot is outside its window, say false. If you check everyone, say true.

The note under each spot in the animation is its window. The pile on the side is the list of helpers still waiting, which is the recursion.

class Solution {
    public boolean isValidBST(TreeNode root) {
        return fits(root, null, null);
    }

    // low and high are the window; null means "no limit"
    private boolean fits(TreeNode node, Integer low, Integer high) {
        if (node == null) return true;
        if (low != null && node.val <= low) return false;
        if (high != null && node.val >= high) return false;
        return fits(node.left, low, node.val)      // left: high end tightens
            && fits(node.right, node.val, high);   // right: low end tightens
    }
}

How long it takes: every spot is checked once, O(n). Extra room: the recursion depth, O(h). Using null for "no limit" avoids the bug where a real value equals Integer.MIN_VALUE or Integer.MAX_VALUE.

Another way: the sorted walk

Read the tree left side, then the spot, then the right side. In a BST this always gives a strictly growing row. So walk in that order and check each number against the one before it. This version uses a stack instead of recursion, which interviewers like to see.

import java.util.*;

class Solution {
    public boolean isValidBST(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        Integer prev = null;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {           // go left as far as you can
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();              // the next number in sorted order
            if (prev != null && curr.val <= prev) return false;
            prev = curr.val;
            curr = curr.right;
        }
        return true;
    }
}

Same cost: O(n) time and O(h) room.

Watch out for

• Starting the window at Integer.MIN_VALUE and Integer.MAX_VALUE with <= and >=. A tree [2147483647] then fails. Use Integer with null, or long bounds.
• Duplicates: use <= and >= in the failure checks unless the problem says duplicates are allowed on one side.
• Keeping prev as a field in the sorted walk and forgetting to reset it between test calls.

What interviewers ask next

• Return the size of the largest part of a tree that is a BST. Do it bottom up: each spot returns its size, min, max and whether it is a BST. See "Largest BST in a Binary Tree".
• Two spots of a BST were swapped by mistake. Fix it. In the sorted walk, find the one or two places where the row goes down, and swap the first big one with the last small one.
• Can you do it in O(1) extra room? Yes, with a Morris walk that temporarily threads each spot's predecessor back to it. Still O(n) time.
• Which way stops earlier on a bad tree? Both stop at the first broken spot they meet, but they meet spots in different orders.

Remember this

Grown-up words: the rule card is a pair of bounds (low, high), copying and tightening it on the way down is depth first search with bounds, the waiting helpers are the call stack, the sorted walk is an inorder traversal, and a strictly growing row is a strictly increasing sequence.