Largest BST in a Binary Tree

The problem, simply

You get a binary tree. Some parts of it may follow the binary search tree (BST) rule: everything on the left side of a spot is smaller and everything on the right side is bigger. Find the largest such part and return how many spots it has.

A "part" here means a spot together with everything below it (a subtree). You cannot pick and choose spots.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each spot, check from scratch whether its part is a BST. If yes, count it. If not, look further down.

1. If the part under this spot is a BST (use the "window" check from "Check if a tree is a BST or not"), return its size.
2. Otherwise return the bigger answer of the left side and the right side.

class Solution {
    public int largestBst(TreeNode root) {
        if (root == null) return 0;
        if (isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)) return size(root);
        return Math.max(largestBst(root.left), largestBst(root.right));
    }

    private boolean isBST(TreeNode n, long low, long high) {
        if (n == null) return true;
        if (n.val <= low || n.val >= high) return false;
        return isBST(n.left, low, n.val) && isBST(n.right, n.val, high);
    }

    private int size(TreeNode n) {
        return n == null ? 0 : 1 + size(n.left) + size(n.right);
    }
}

How long it takes: a check at a spot costs the size of its part. In a stick shaped tree that is broken at the bottom, the parts have sizes n, n - 1, ..., 1, so O(n^2). Extra room: the recursion, O(h).

Way 2: the clever way

Work from the bottom up, and let every spot send one report to its parent: is my part a BST, how big is it, and what are its smallest and biggest numbers.

1. An empty spot reports: "BST, size 0, smallest +infinity, biggest -infinity". These fake values make every comparison above it pass.
2. A spot first gets the reports from its left and right side.
3. Its part is a BST if both sides are BSTs, and left.biggest < me < right.smallest.
4. If yes, report size 1 + left.size + right.size, smallest min(me, left.smallest), biggest max(me, right.biggest), and update the best answer.
5. If no, report "not a BST". The parent will then fail too.

class Solution {
    // the report each spot sends up
    static class Info {
        boolean bst;
        int size;
        long min, max;
        Info(boolean bst, int size, long min, long max) {
            this.bst = bst; this.size = size; this.min = min; this.max = max;
        }
    }

    private int best;

    public int largestBst(TreeNode root) {
        best = 0;
        report(root);
        return best;
    }

    private Info report(TreeNode node) {
        if (node == null) return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);
        Info l = report(node.left);
        Info r = report(node.right);
        if (l.bst && r.bst && l.max < node.val && node.val < r.min) {
            int size = 1 + l.size + r.size;
            best = Math.max(best, size);
            return new Info(true, size, Math.min(node.val, l.min), Math.max(node.val, r.max));
        }
        return new Info(false, 0, 0, 0);       // broken: the parent will be broken too
    }
}

How long it takes: every spot makes one report from two smaller reports, O(n). Extra room: the recursion, O(h).

Watch out for

• The empty report must use "smallest = +infinity, biggest = -infinity", so a leaf passes the test. Using long avoids trouble when a real value is Integer.MIN_VALUE or Integer.MAX_VALUE.
• For the smallest of a valid part, use min(me, left.min), not left.min alone. With an empty left side, left.min is +infinity.
• When a part is broken, its parent is broken too. You do not need to pass sizes up, because best already remembers them.

What interviewers ask next

• Return the largest BST's top spot, not its size. Store the spot together with best.
• Largest BST by sum of values instead of size (LeetCode 1373). Carry sum in the report instead of size, and remember the biggest sum, which may be 0 if all values are negative.
• Count how many parts are BSTs. Add 1 each time a report says "BST".
• Why not top down? A top down check repeats work for every spot. Bottom up, each spot reuses its children's answers. This "collect info from children, then decide" pattern solves many tree problems: diameter, balanced check, maximum path sum.

Remember this

Grown-up words: a team under a coach is a subtree, sending reports up from the bottom is a postorder traversal, the report is a tuple of return values, and reusing children's answers is the "tree DP" pattern.