☕ DSA Java Articles

Topics › Binary Search Trees › Practice Problems

Size of the largest BST in a Binary Tree

Hard TUF ID 2773 SDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the root of a binary tree that is not necessarily a binary search tree. Find the largest subtree that is a valid BST and return its number of nodes.

Two details decide the answer:

An empty tree has answer 0; any single node is a BST of size 1.

Constraints (LeetCode 333 / GFG “Largest BST”): up to 10^5 nodes; keys fit in a 32-bit int.

Example 1

        10
       /  \
      5    15
     / \     \
    1   8     7

answer = 3        // the subtree rooted at 5: {1, 5, 8}

The whole tree fails because 7 sits in the right subtree of 15 but is smaller than it.

Example 2

        10
       /  \
      5    15
     / \
    1   12

answer = 3        // the subtree rooted at 5: {1, 5, 12}

Every parent-child pair looks fine locally, yet the whole tree is not a BST: 12 is in the left subtree of 10 but larger than it. A solution that only compares neighbours would wrongly answer 5.

Approach 1: Brute force, validate every subtree

Intuition. Ask the question literally at each node: “is the subtree rooted here a BST?” To validate it correctly, pass down an open interval (lo, hi) that every key must lie in. The root may be anything; a left child must lie below its parent and inherit the parent’s lower bound; a right child must lie above its parent and inherit the upper bound. That carries the global rule from Example 2 down to every descendant.

One shortcut makes the search cleaner. If the subtree at a node is a BST, every BST strictly inside it is smaller, so we return its size right away and do not look inside. Only when the check fails do we recurse into the two children and keep the better result.

Algorithm.

  1. If the node is null, return 0.
  2. If isBST(node, -∞, +∞), return size(node).
  3. Otherwise return the maximum of the answers for the left and right children.

isBST(node, lo, hi) returns true for null, false if node.val is not strictly between lo and hi, and otherwise checks the left child with (lo, node.val) and the right with (node.val, hi). The bounds are long, so keys equal to Integer.MIN_VALUE or Integer.MAX_VALUE are still strictly inside the starting interval.

static int bruteForce(TreeNode root) {
    if (root == null) return 0;
    if (isBST(root, Long.MIN_VALUE, Long.MAX_VALUE)) return size(root);   // nothing strictly inside can be larger
    return Math.max(bruteForce(root.left), bruteForce(root.right));
}

static boolean isBST(TreeNode node, long lo, long hi) {          // every key must lie strictly between lo and hi
    if (node == null) return true;
    if (node.val <= lo || node.val >= hi) return false;
    return isBST(node.left, lo, node.val) && isBST(node.right, node.val, hi);
}

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

Complexity. Time O(n · h): a failing validation at a node can scan most of its subtree, and every node lies in at most h + 1 subtrees. On a skewed tree that is O(n^2). Space O(h) for the recursion.

The waste is clear: the validation at a node re-examines all the keys that were already examined when validating its descendants.

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

Intuition. Flip the direction. Instead of each node asking about everything below it, let each subtree report a small summary upward, and let the parent decide in O(1) using only its two children’s summaries.

What does a parent need to know to decide whether it is the root of a BST?

If all three hold, the parent’s subtree is a BST whose size is leftSize + rightSize + 1, whose minimum is the left side’s minimum (or the parent itself if the left is empty), and whose maximum is the right side’s maximum (or the parent itself). That is exactly the summary the grandparent will need, so the information flows bottom-up in a single post-order traversal.

The empty subtree needs a summary that never blocks its parent: report min = +∞ and max = -∞. Then left.max < node.val and node.val < right.min are automatically true, and Math.min(left.min, node.val) correctly picks the node’s own key. Storing these as long keeps the sentinels distinct from every real int key.

A subtree that is not a BST makes every ancestor fail too, because each ancestor’s subtree contains it. So the summary for such a subtree just says isBST = false. A common alternative encodes “not a BST” as min = -∞, max = +∞, which makes the parent’s comparison fail on its own; the explicit flag is easier to read.

Here is the summary type:

static final class Info {
    final boolean isBST;
    final int size;
    final long min, max;

    Info(boolean isBST, int size, long min, long max) {
        this.isBST = isBST;
        this.size = size;
        this.min = min;
        this.max = max;
    }
}

Algorithm.

  1. summarize(null) returns (isBST = true, size = 0, min = +∞, max = -∞).
  2. For a real node, summarise the left child and then the right child.
  3. If both are BSTs and left.max < node.val < right.min: compute the size, update the global best, and return the combined summary.
  4. Otherwise return isBST = false.
  5. The answer is the best size seen, 0 for an empty tree.
static int optimal(TreeNode root) {
    int[] best = {0};
    summarize(root, best);
    return best[0];
}

static Info summarize(TreeNode node, int[] best) {
    if (node == null) return new Info(true, 0, Long.MAX_VALUE, Long.MIN_VALUE);   // empty: fits under any parent
    Info l = summarize(node.left, best);
    Info r = summarize(node.right, best);
    if (l.isBST && r.isBST && l.max < node.val && node.val < r.min) {
        int size = l.size + r.size + 1;
        best[0] = Math.max(best[0], size);
        return new Info(true, size, Math.min(l.min, node.val), Math.max(r.max, node.val));
    }
    return new Info(false, 0, 0, 0);                 // no ancestor can be a BST either
}

Dry run on Example 1, in post-order:

node left summary right summary BST here? size range
1 empty empty yes 1 [1, 1]
8 empty empty yes 1 [8, 8]
5 [1, 1] [8, 8] 1 < 5 < 8, yes 3 [1, 8]
7 empty empty yes 1 [7, 7]
15 empty [7, 7] 15 < 7 fails    
10 [1, 8] not a BST no    

The best size recorded is 3, at node 5.

On Example 2, node 5 reports range [1, 12]. At the root, left.max = 12 is not smaller than 10, so the root fails, which is exactly the global check that neighbour comparisons miss.

Complexity. Time O(n): each node is visited once and does constant work. Space O(h) for the recursion stack. A degenerate chain of 10^5 nodes can exceed Java’s default stack; if that matters, run the same logic with an explicit post-order stack or in a thread with a larger stack size.

Edge cases and pitfalls