Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Largest BST Subtree

HARDProblemSolveExternal Links

Description

You are given the root of a binary tree (not necessarily a BST). Your task is to find the size of the largest subtree within this binary tree that is also a valid Binary Search Tree (BST).

The size of a subtree is defined as the number of nodes it contains.

A subtree rooted at some node is considered a valid BST if for every node in that subtree:

  • All values in the left subtree are strictly less than the node's value
  • All values in the right subtree are strictly greater than the node's value
  • Both the left and right subtrees are themselves valid BSTs
  • No duplicate values exist in the subtree

Note that a single leaf node is always a valid BST of size 1.

Examples

Example 1

Input: root = [5, 2, 4, 1, 3]

Output: 3

Explanation: The tree looks like this:

       5
      / \
     2   4
    / \
   1   3

The subtree rooted at node 2 is a valid BST: left child 1 < 2 and right child 3 > 2, with inorder [1, 2, 3]. Its size is 3.

The full tree rooted at 5 is NOT a valid BST because the right child 4 < 5, but a right-subtree value must be > the root. Node 4 alone is a valid BST of size 1.

The largest BST subtree has size 3 (rooted at node 2).

Example 2

Input: root = [6, 7, 3, null, 2, 2, 4]

Output: 3

Explanation: The tree looks like this:

       6
      / \
     7   3
      \ / \
      2 2   4

The subtree rooted at node 3 is a valid BST: left child 2 < 3 and right child 4 > 3, with inorder [2, 3, 4]. Its size is 3.

The subtree rooted at node 7 is NOT a valid BST because its right child 2 < 7 (a right child must be greater).

The largest BST subtree has size 3 (rooted at node 3).

Example 3

Input: root = [3, 1, 5, null, 2, 4, 6]

Output: 7

Explanation: The tree looks like this:

       3
      / \
     1   5
      \ / \
      2 4   6

The entire tree is a valid BST. Every node satisfies the BST property. The inorder traversal is [1, 2, 3, 4, 5, 6] — strictly increasing. The largest BST subtree is the entire tree itself with size 7.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 1 ≤ node.data ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward approach is to examine every node in the tree and ask: "Is the subtree rooted at this node a valid BST?" If it is, we count how many nodes it has. We keep track of the maximum size seen across all nodes.

Think of a building inspector who visits every room in a building and performs a full safety inspection of the entire wing starting from that room. Even if two rooms share the same wing, the inspector rechecks everything from scratch each time. This is clearly wasteful — the inspector re-inspects overlapping areas repeatedly — but it is thorough and correct.

To check if a subtree rooted at a node is a valid BST, we recursively verify that every node satisfies the min/max range constraint: each node's value must fall within an allowed range determined by its ancestors. If a node violates this range, the subtree is not a BST.

For each of the n nodes, this BST validation can take up to O(n) time (for the subtree rooted there), leading to O(n²) total work in the worst case.

Step-by-Step Explanation

Let's trace through Example 1: root = [5, 2, 4, 1, 3]

Tree structure:

       5
      / \
     2   4
    / \
   1   3

Step 1: Start at node 5. Check if the full tree rooted at 5 is a valid BST.

  • Node 5 with range (-∞, +∞): 5 is within range ✓
  • Left child 2 with range (-∞, 5): 2 < 5 ✓
  • Left of 2: node 1 with range (-∞, 2): 1 < 2 ✓ (leaf, valid)
  • Right of 2: node 3 with range (2, 5): 2 < 3 < 5 ✓ (leaf, valid)
  • Right child 4 with range (5, +∞): 4 > 5? NO! 4 < 5 ✗
  • Subtree at 5 is NOT a valid BST.

Step 2: Check node 2. Is the subtree rooted at 2 a valid BST?

  • Node 2 with range (-∞, +∞): valid ✓
  • Left child 1 with range (-∞, 2): 1 < 2 ✓
  • Right child 3 with range (2, +∞): 3 > 2 ✓
  • All nodes pass! Subtree at 2 IS a BST. Count nodes: 3. Update max_size = 3.

Step 3: Check node 4. It is a leaf — trivially a BST of size 1. max_size remains 3.

Step 4: Check node 1. Leaf — BST of size 1. max_size remains 3.

Step 5: Check node 3. Leaf — BST of size 1. max_size remains 3.

Result: The largest BST subtree has size 3, rooted at node 2.

Brute Force — Checking Each Subtree for BST Validity — Watch how the brute force approach visits each node and checks whether its entire subtree forms a valid BST, tracking the maximum BST size found.

Algorithm

  1. Initialize max_size = 0
  2. For each node in the tree (via any traversal):
    • Call isBST(node, min, max) to check if the subtree is a valid BST using range validation
    • If valid, call countNodes(node) to count subtree size
    • Update max_size = max(max_size, subtree_size)
  3. Return max_size

Helper isBST(node, min_val, max_val):

  • If node is null, return true
  • If node.val ≤ min_val or node.val ≥ max_val, return false
  • Return isBST(left, min_val, node.val) AND isBST(right, node.val, max_val)

Helper countNodes(node):

  • If node is null, return 0
  • Return 1 + countNodes(left) + countNodes(right)

Code

class Solution {
public:
    int largestBst(Node* root) {
        int maxSize = 0;
        traverse(root, maxSize);
        return maxSize;
    }

private:
    void traverse(Node* node, int& maxSize) {
        if (node == nullptr) return;

        if (isBST(node, INT_MIN, INT_MAX)) {
            int size = countNodes(node);
            maxSize = max(maxSize, size);
        }

        traverse(node->left, maxSize);
        traverse(node->right, maxSize);
    }

    bool isBST(Node* node, int minVal, int maxVal) {
        if (node == nullptr) return true;
        if (node->data <= minVal || node->data >= maxVal) return false;
        return isBST(node->left, minVal, node->data) &&
               isBST(node->right, node->data, maxVal);
    }

    int countNodes(Node* node) {
        if (node == nullptr) return 0;
        return 1 + countNodes(node->left) + countNodes(node->right);
    }
};
class Solution:
    def largestBst(self, root):
        self.max_size = 0

        def is_bst(node, min_val, max_val):
            if not node:
                return True
            if node.data <= min_val or node.data >= max_val:
                return False
            return (is_bst(node.left, min_val, node.data) and
                    is_bst(node.right, node.data, max_val))

        def count_nodes(node):
            if not node:
                return 0
            return 1 + count_nodes(node.left) + count_nodes(node.right)

        def traverse(node):
            if not node:
                return
            if is_bst(node, float('-inf'), float('inf')):
                size = count_nodes(node)
                self.max_size = max(self.max_size, size)
            traverse(node.left)
            traverse(node.right)

        traverse(root)
        return self.max_size
class Solution {
    static int maxSize;

    static int largestBst(Node root) {
        maxSize = 0;
        traverse(root);
        return maxSize;
    }

    static void traverse(Node node) {
        if (node == null) return;

        if (isBST(node, Integer.MIN_VALUE, Integer.MAX_VALUE)) {
            int size = countNodes(node);
            maxSize = Math.max(maxSize, size);
        }

        traverse(node.left);
        traverse(node.right);
    }

    static boolean isBST(Node node, int minVal, int maxVal) {
        if (node == null) return true;
        if (node.data <= minVal || node.data >= maxVal) return false;
        return isBST(node.left, minVal, node.data) &&
               isBST(node.right, node.data, maxVal);
    }

    static int countNodes(Node node) {
        if (node == null) return 0;
        return 1 + countNodes(node.left) + countNodes(node.right);
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n nodes, we potentially validate the entire subtree rooted at it, which can take up to O(n) time. In the worst case (e.g., a skewed tree where every prefix is a valid BST), this results in O(n) validations each costing O(n), giving O(n²) total.

Additionally, countNodes also traverses the subtree, but this is dominated by the validation cost.

Space Complexity: O(h)

The recursion stack depth is bounded by the height of the tree. For a balanced tree h = O(log n), for a skewed tree h = O(n). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force approach performs redundant work. When we check if the subtree rooted at the parent is a BST, we recursively validate all children. Then when we move to each child, we validate their subtrees again from scratch.

For example, when checking if node 5's subtree is a BST, we already validate nodes 2, 1, and 3. But then we separately check node 2's subtree again, re-validating nodes 1 and 3.

With n up to 10^5 nodes, O(n²) means up to 10^10 operations — far too slow for typical time limits.

The key insight is: instead of checking top-down (parent first, then children), we can work bottom-up (children first, then parent). If we already know whether each child's subtree is a valid BST along with its size, min value, and max value, we can determine the parent's BST status in O(1) time. This eliminates all redundant work, reducing total time to O(n).

Optimal Approach - Bottom-Up Post-Order Traversal

Intuition

Instead of asking "is this subtree a BST?" top-down for every node (which re-examines the same nodes repeatedly), we flip the direction: process children first, then combine their results at the parent.

Imagine a company where each department reports its performance up to its manager. The manager does not re-audit every employee — they just look at the two department reports and decide the combined status. This bottom-up reporting is efficient because each employee is reviewed exactly once.

For each node, its children return a small summary:

  • Is my subtree a valid BST?
  • How many nodes are in my subtree?
  • What is the minimum value in my subtree?
  • What is the maximum value in my subtree?

The parent then checks:

  1. Left subtree is a BST AND right subtree is a BST
  2. My value is greater than the maximum value in my left subtree (left_max < node.val)
  3. My value is less than the minimum value in my right subtree (node.val < right_min)

If all three conditions hold, the parent's subtree is also a valid BST with size = 1 + left_size + right_size, and min/max are updated accordingly.

If any condition fails, the parent's subtree is NOT a BST, but we still propagate the best BST size found so far among the children.

Step-by-Step Explanation

Let's trace through Example 1: root = [5, 2, 4, 1, 3]

Tree structure:

       5
      / \
     2   4
    / \
   1   3

We use post-order traversal (left → right → node). Each node returns (is_bst, size, min_val, max_val).

Step 1: Visit node 1 (leaf). No children → trivially a BST.

  • Return: (is_bst=true, size=1, min=1, max=1)

Step 2: Visit node 3 (leaf). No children → trivially a BST.

  • Return: (is_bst=true, size=1, min=3, max=3)

Step 3: Visit node 2. Left child returned (true, 1, 1, 1). Right child returned (true, 1, 3, 3).

  • Left is BST? Yes ✓
  • Right is BST? Yes ✓
  • node.val(2) > left_max(1)? Yes ✓ (2 > 1)
  • node.val(2) < right_min(3)? Yes ✓ (2 < 3)
  • All conditions pass! Subtree at 2 IS a BST.
  • Size = 1 + 1 + 1 = 3, min = 1, max = 3.
  • Update global max_bst_size = 3.
  • Return: (is_bst=true, size=3, min=1, max=3)

Step 4: Visit node 4 (leaf). No children → trivially a BST.

  • Return: (is_bst=true, size=1, min=4, max=4)

Step 5: Visit node 5. Left child returned (true, 3, 1, 3). Right child returned (true, 1, 4, 4).

  • Left is BST? Yes ✓
  • Right is BST? Yes ✓
  • node.val(5) > left_max(3)? Yes ✓ (5 > 3)
  • node.val(5) < right_min(4)? NO ✗ (5 > 4, but we need 5 < 4)
  • Condition fails! Subtree at 5 is NOT a BST.
  • Return: (is_bst=false, size=0, min=0, max=0)
  • Global max_bst_size stays at 3.

Result: The largest BST subtree has size 3.

Bottom-Up Post-Order — Efficient BST Size Detection — Watch how post-order traversal processes children before parents, combining BST status and size information bottom-up so each node is visited exactly once.

Algorithm

  1. Define a helper function that returns a tuple (is_bst, size, min_val, max_val) for each node
  2. Base case: If node is null, return (true, 0, +∞, -∞)
    • Using +∞ for min and -∞ for max ensures any parent's value will satisfy the range check
  3. Recursively get results for left and right children (post-order)
  4. Check BST validity at current node:
    • left.is_bst AND right.is_bst
    • node.val > left.max_val (current value greater than all left subtree values)
    • node.val < right.min_val (current value less than all right subtree values)
  5. If valid BST:
    • size = 1 + left.size + right.size
    • min_val = min(left.min_val, node.val)
    • max_val = max(right.max_val, node.val)
    • Update global max_bst_size if size is larger
    • Return (true, size, min_val, max_val)
  6. If NOT a valid BST:
    • Return (false, 0, 0, 0) — the parent cannot form a BST either
  7. Return max_bst_size

Code

class Solution {
public:
    int maxBstSize = 0;

    int largestBst(Node* root) {
        maxBstSize = 0;
        solve(root);
        return maxBstSize;
    }

private:
    // Returns {is_bst, size, min_val, max_val}
    tuple<bool, int, int, int> solve(Node* node) {
        if (node == nullptr) {
            return {true, 0, INT_MAX, INT_MIN};
        }

        auto [leftBst, leftSize, leftMin, leftMax] = solve(node->left);
        auto [rightBst, rightSize, rightMin, rightMax] = solve(node->right);

        if (leftBst && rightBst &&
            node->data > leftMax && node->data < rightMin) {
            int size = 1 + leftSize + rightSize;
            maxBstSize = max(maxBstSize, size);
            int minVal = min(leftMin, node->data);
            int maxVal = max(rightMax, node->data);
            return {true, size, minVal, maxVal};
        }

        return {false, 0, 0, 0};
    }
};
class Solution:
    def largestBst(self, root):
        self.max_bst_size = 0

        def solve(node):
            # Returns (is_bst, size, min_val, max_val)
            if not node:
                return (True, 0, float('inf'), float('-inf'))

            left_bst, left_size, left_min, left_max = solve(node.left)
            right_bst, right_size, right_min, right_max = solve(node.right)

            if (left_bst and right_bst and
                    node.data > left_max and node.data < right_min):
                size = 1 + left_size + right_size
                self.max_bst_size = max(self.max_bst_size, size)
                min_val = min(left_min, node.data)
                max_val = max(right_max, node.data)
                return (True, size, min_val, max_val)

            return (False, 0, 0, 0)

        solve(root)
        return self.max_bst_size
class Solution {
    static int maxBstSize;

    static int largestBst(Node root) {
        maxBstSize = 0;
        solve(root);
        return maxBstSize;
    }

    // Returns int[] = {is_bst (0 or 1), size, min_val, max_val}
    static int[] solve(Node node) {
        if (node == null) {
            return new int[]{1, 0, Integer.MAX_VALUE, Integer.MIN_VALUE};
        }

        int[] left = solve(node.left);
        int[] right = solve(node.right);

        if (left[0] == 1 && right[0] == 1 &&
            node.data > left[3] && node.data < right[2]) {
            int size = 1 + left[1] + right[1];
            maxBstSize = Math.max(maxBstSize, size);
            int minVal = Math.min(left[2], node.data);
            int maxVal = Math.max(right[3], node.data);
            return new int[]{1, size, minVal, maxVal};
        }

        return new int[]{0, 0, 0, 0};
    }
}

Complexity Analysis

Time Complexity: O(n)

We perform a single post-order traversal, visiting each of the n nodes exactly once. At each node, we do O(1) work: a few comparisons and arithmetic operations to combine children's results. Total time is O(n), a dramatic improvement over the brute force's O(n²).

For n = 10^5, this means ~10^5 operations instead of ~10^10 — the difference between milliseconds and minutes.

Space Complexity: O(h)

The space is used by the recursion call stack, which goes as deep as the height h of the tree. For a balanced tree, h = O(log n) ≈ 17 for n = 10^5. For a skewed tree, h = O(n) in the worst case. Each recursive call stores a constant amount of data (the 4-element tuple), so total space is O(h).