☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Largest BST in Binary Tree

Hard TUF ID 98 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree (not necessarily a BST). Return the number of nodes in the largest subtree that is a valid binary search tree. A subtree here means a node together with all of its descendants; you may not cut off part of it. The BST rule is strict: every key in a left subtree is smaller than the node, every key in a right subtree is larger, so duplicates break it. An empty tree has answer 0.

Constraints (LeetCode version): up to 10^4 nodes with keys in [-10^4, 10^4]. The code below is correct for any 32-bit keys.

Example 1

        10
       /  \
      5    15
     / \     \
    1   8     7
answer = 3       // the subtree {5, 1, 8}

The whole tree is not a BST because 7 is in the right subtree of 15 but smaller than it. The subtree at 15 fails for the same reason. The subtree at 5 is a BST of size 3, and every leaf is a BST of size 1.

Example 2

        3
       / \
      2   4
         /
        1
answer = 2       // the subtree {4, 1}

At the root, 2 < 3 < 4 looks fine, but 1 sits in the right subtree of 3. The subtree at 4 is a BST, since 1 < 4, and has size 2.

Approach 1: Brute force, validate every subtree

Intuition. We already know how to check whether one tree is a BST: pass an allowed range down the recursion. So try every node as the root of a candidate subtree. Work from the top: if the subtree at root is a BST, nothing inside it can be bigger, so its size is the answer for this branch. Otherwise the answer lies entirely in the left or the right subtree, and we recurse.

Algorithm.

  1. An empty tree has answer 0.
  2. If the subtree at root passes isBST with range (-∞, +∞), return its node count.
  3. Otherwise return the larger of the answers for the two children.
static int bruteForce(TreeNode root) {
    if (root == null) return 0;
    if (isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)) return count(root);   // nothing below can be bigger
    return Math.max(bruteForce(root.left), bruteForce(root.right));
}

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

static int count(TreeNode node) {
    return node == null ? 0 : 1 + count(node.left) + count(node.right);
}

Complexity. Time O(n^2) in the worst case. Each isBST call can scan the whole subtree before finding a violation. Picture a left chain whose bottom leaf breaks the order: every node’s check scans down to the bottom, about n^2 / 2 steps in total. Space O(h) for the recursion.

The waste is that a node’s validation re-examines every node below it, which its children’s validations already did.

Approach 2: Optimal, one post-order pass with subtree summaries

Intuition. Turn the question around and go bottom-up. A subtree rooted at node is a BST exactly when:

  1. its left subtree is a BST,
  2. its right subtree is a BST,
  3. the largest key on the left is smaller than node.val, and the smallest key on the right is larger.

If each child reports (min key, max key, size), the parent can decide all three in O(1). So each subtree returns a small summary:

Two sentinel tricks keep the code free of special cases:

The sentinels are long values outside the int range, so a real key such as Integer.MAX_VALUE can never collide with them.

Algorithm.

  1. summarize(null) returns (+∞, -∞, 0).
  2. For a node, summarize the left and right children first (post-order).
  3. If left.max < node.val < right.min, return (min(left.min, node.val), max(right.max, node.val), left.size + right.size + 1).
  4. Otherwise return (-∞, +∞, max(left.size, right.size)).
  5. The answer is summarize(root).size.
static class Info {
    final long min, max;   // smallest and largest key in the subtree
    final int size;        // size of the largest BST inside the subtree
    Info(long min, long max, int size) { this.min = min; this.max = max; this.size = size; }
}

The pass itself is a post-order recursion that builds a summary from the two child summaries:

static int optimal(TreeNode root) {
    return summarize(root).size;
}

static Info summarize(TreeNode node) {
    if (node == null) return new Info(Long.MAX_VALUE, Long.MIN_VALUE, 0);   // empty: fits under any parent
    Info left = summarize(node.left);
    Info right = summarize(node.right);
    if (left.max < node.val && node.val < right.min) {                      // node joins two BSTs into one
        return new Info(Math.min(left.min, node.val), Math.max(right.max, node.val), left.size + right.size + 1);
    }
    return new Info(Long.MIN_VALUE, Long.MAX_VALUE, Math.max(left.size, right.size));
}

When the subtree is a BST, left.size and right.size are the full sizes of the two children, because a child that is not a BST would have made the check fail. That is why adding them plus one gives the size of the whole subtree.

The min(left.min, node.val) matters when the left side is empty: left.min is +∞, so the minimum must come from node.val. The same holds for the maximum on the right.

Dry run on Example 1 (∞ written for the sentinels):

node left summary right summary BST here? returned (min, max, size)
1 empty empty yes (1, 1, 1)
8 empty empty yes (8, 8, 1)
5 (1, 1, 1) (8, 8, 1) 1 < 5 < 8, yes (1, 8, 3)
7 empty empty yes (7, 7, 1)
15 empty (7, 7, 1) 15 < 7? no (-∞, +∞, 1)
10 (1, 8, 3) (-∞, +∞, 1) 10 < -∞? no (-∞, +∞, 3)

The answer is 3.

Complexity. Time O(n): every node is summarised once with constant work. Space O(h) for the recursion; each call allocates one small Info object, which is garbage as soon as the parent reads it.

Edge cases and pitfalls