Largest BST Subtree

Medium · Graphs · Explanation and code example

Post-Order Traversal

How it works

The key insight is that we can determine if a subtree is a valid BST by looking at information from its children. If we process nodes bottom-up (post-order), each node can inherit the min/max values and sizes from its children. A node forms a valid BST if the maximum value in its left subtree is less than the node, and the minimum value in its right subtree is greater than the node. By returning both the valid range and size from each recursive call, we avoid redundant traversals.

Steps

  1. Define a helper function that returns three values for each node: minimum value, maximum value, and the size of the largest BST in that subtree.
  2. For an empty node, return values that indicate a valid empty BST (min = infinity, max = negative infinity, size = 0).
  3. Recursively process left and right children first.
  4. If the current node is greater than the left max and less than the right min:
    • The subtree rooted here is a valid BST.
    • Return updated min/max bounds and the combined size.
  5. Otherwise, return invalid bounds (to prevent parent from being a valid BST) and the maximum size found so far.

Complexity

  • Time complexity: O(N)
  • Space complexity: O(N)
    • The recursion call stack can take at most O(H) space; in the worst-case scenario, the height of the tree will equal N.

Where N and H are the number of nodes and the max height of the given tree respectively

Things to watch for

Only Checking Immediate Children Instead of Entire Subtrees

A subtree is a valid BST only if all nodes in the left subtree are smaller than the root and all nodes in the right subtree are larger. Checking only the immediate left and right children misses violations deeper in the tree. Always propagate min/max bounds through the entire subtree to validate correctly.

Confusing BST Validity with Binary Tree Structure

A binary tree where each node has at most two children is not automatically a BST. The BST property requires strict ordering across entire subtrees, not just parent-child relationships. Do not assume validity based on tree shape alone; always verify the ordering constraint.

Returning Wrong Size When Subtree Is Not a Valid BST

When a subtree fails the BST check, its size should not be counted as a valid BST. Instead, return the maximum size found in its left or right child subtrees. Mixing up the return values causes incorrect propagation and wrong final answers.

Python code example

from typing import Optional

# Each node will return min node value, max node value, size
class NodeValue:
    def __init__(self, min_node, max_node, max_size):
        self.max_node = max_node
        self.min_node = min_node
        self.max_size = max_size

class Solution:
    def largest_bst_subtree_helper(self, root):
        # An empty tree is a BST of size 0.
        if not root:
            return NodeValue(float('inf'), float('-inf'), 0)

        # Get values from left and right subtree of current tree.
        left = self.largest_bst_subtree_helper(root.left)
        right = self.largest_bst_subtree_helper(root.right)

        # Current node is greater than max in left AND smaller than min in right, it is a BST.
        if left.max_node < root.val < right.min_node:
            # It is a BST.
            return NodeValue(min(root.val, left.min_node), max(root.val, right.max_node),
                             left.max_size + right.max_size + 1)

        # Otherwise, return [-inf, inf] so that parent can't be valid BST
        return NodeValue(float('-inf'), float('inf'), max(left.max_size, right.max_size))

    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        return self.largest_bst_subtree_helper(root).max_size

C++ code example

// Each node will return min node value, max node value, max size
class NodeValue {
public:
    int maxNode, minNode, maxSize;

    NodeValue(int minNode, int maxNode, int maxSize) {
        this->maxNode = maxNode;
        this->minNode = minNode;
        this->maxSize = maxSize;
    }
};

class Solution {
public:
    NodeValue largestBSTSubtreeHelper(TreeNode* root) {
        // An empty tree is a BST of size 0.
        if (!root) {
            return NodeValue(INT_MAX, INT_MIN, 0);
        }

        // Get values from left and right subtree of current tree.
        auto left = largestBSTSubtreeHelper(root->left);
        auto right = largestBSTSubtreeHelper(root->right);

        // Current node is greater than max in left AND smaller than min in right, it is a BST.
        if (left.maxNode < root->val && root->val < right.minNode) {
            // It is a BST.
            return NodeValue(min(root->val, left.minNode), max(root->val, right.maxNode),
                            left.maxSize + right.maxSize + 1);
        }

        // Otherwise, return [-inf, inf] so that parent can't be valid BST
        return NodeValue(INT_MIN, INT_MAX, max(left.maxSize, right.maxSize));
    }

    int largestBSTSubtree(TreeNode* root) {
        return largestBSTSubtreeHelper(root).maxSize;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations