LeetCode 333: Largest BST Subtree

Problem Restatement

We are given the root of a binary tree.

We need to find the size of the largest subtree that is also a valid Binary Search Tree (BST).

The size of a subtree means the number of nodes inside it.

A BST follows these rules:

The subtree does not need to include the original root. Any connected subtree inside the tree may be the answer.

Input and Output

Function shape:

def largestBSTSubtree(root: Optional[TreeNode]) -> int:
    ...

Examples

Example 1:

Input:
        10
       /  \
      5   15
     / \    \
    1   8    7

Output: 3

The subtree:

      5
     / \
    1   8

is a valid BST of size 3.

The whole tree is not a BST because:

7 < 15

but 7 appears in the right subtree of 15.

So the answer is 3.

Example 2:

Input:
    2
   / \
  1   3

Output: 3

The whole tree is a valid BST.

First Thought: Validate Every Subtree

A direct idea is:

1. For every node, treat it as the root of a subtree.
2. Check whether that subtree is a BST.
3. Count its nodes.
4. Keep the maximum size.

To validate a BST, we can recursively check value ranges.

But this repeats work many times.

For example, the same subtree may be validated again and again from different ancestors.

The worst-case complexity becomes:

O(n^2)

We need one DFS traversal that computes everything bottom-up.

Key Insight

Use postorder traversal.

For each subtree, return enough information so the parent can decide whether the current subtree forms a BST.

For every node, we need four pieces of information:

Suppose we already know the information for the left subtree and the right subtree.

The current subtree is a BST if:

left subtree is BST
right subtree is BST
left.max_value < current node value
current node value < right.min_value

If true:

current size =
left size + right size + 1

Otherwise, the current subtree is not a BST.

This is a classic bottom-up tree DP.

Algorithm

Run DFS in postorder.

For each node:

1. Recursively process the left subtree.
2. Recursively process the right subtree.
3. Check whether the current subtree satisfies BST conditions.
4. If valid:
   1. Compute subtree size.
   2. Update the global answer.
   3. Return subtree information.
5. Otherwise:
   1. Return information marking the subtree as invalid.

For null nodes:

empty subtree is a valid BST

with:

size = 0
min_value = +infinity
max_value = -infinity

These extreme values simplify comparisons.

Walkthrough

Use:

        10
       /  \
      5   15
     / \    \
    1   8    7

Start from leaves.

Node 1:

BST
size = 1
min = 1
max = 1

Node 8:

BST
size = 1
min = 8
max = 8

Now process node 5.

Conditions:

1 < 5 < 8

So subtree rooted at 5 is a BST.

Size:

1 + 1 + 1 = 3

Now process node 15.

Its right child is 7.

Condition:

15 < 7

is false.

So subtree rooted at 15 is not a BST.

Finally process node 10.

Its right subtree is already invalid, so the whole tree is invalid.

The largest BST found was the subtree rooted at 5, with size 3.

Correctness

The DFS processes every subtree after processing its children.

For a null subtree, the algorithm returns that it is a valid BST with size 0. This serves as the base case.

Suppose the DFS has already correctly computed information for the left and right subtrees of a node.

The current subtree is a BST exactly when:

left subtree is BST
right subtree is BST
left maximum < current value
current value < right minimum

These are precisely the recursive BST conditions.

If they hold, then combining the left subtree, current node, and right subtree forms a valid BST. The subtree size is:

left size + right size + 1

The subtree minimum becomes the smallest value in the left subtree or the current node. The subtree maximum becomes the largest value in the right subtree or the current node.

If any BST condition fails, then the current subtree cannot be a BST. Returning an invalid marker prevents ancestors from incorrectly using this subtree as part of a larger BST.

Because every subtree is processed exactly once, and every valid BST subtree updates the global maximum size, the final answer equals the size of the largest BST subtree in the tree.

Complexity

In the worst case of a skewed tree:

h = n

Implementation

from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        self.answer = 0

        def dfs(node):
            if node is None:
                return True, 0, float("inf"), float("-inf")

            left_is_bst, left_size, left_min, left_max = dfs(node.left)

            right_is_bst, right_size, right_min, right_max = dfs(node.right)

            if (
                left_is_bst
                and right_is_bst
                and left_max < node.val < right_min
            ):
                size = left_size + right_size + 1

                self.answer = max(self.answer, size)

                return (
                    True,
                    size,
                    min(left_min, node.val),
                    max(right_max, node.val),
                )

            return False, 0, 0, 0

        dfs(root)

        return self.answer

Code Explanation

The global variable stores the best BST size found so far:

self.answer = 0

The DFS returns:

(is_bst, size, min_value, max_value)

For a null node:

return True, 0, float("inf"), float("-inf")

This means:

Then recursively process children:

left_is_bst, left_size, left_min, left_max = dfs(node.left)
right_is_bst, right_size, right_min, right_max = dfs(node.right)

Check BST validity:

left_max < node.val < right_min

If valid:

size = left_size + right_size + 1

Update the global maximum:

self.answer = max(self.answer, size)

Return updated subtree information.

If invalid:

return False, 0, 0, 0

The exact values do not matter because ancestors will reject invalid subtrees immediately.

Testing

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        10,
        TreeNode(
            5,
            TreeNode(1),
            TreeNode(8),
        ),
        TreeNode(
            15,
            None,
            TreeNode(7),
        ),
    )

    assert s.largestBSTSubtree(root) == 3

    root = TreeNode(
        2,
        TreeNode(1),
        TreeNode(3),
    )

    assert s.largestBSTSubtree(root) == 3

    root = TreeNode(1)

    assert s.largestBSTSubtree(root) == 1

    root = TreeNode(
        5,
        TreeNode(4),
        TreeNode(6, TreeNode(3), TreeNode(7)),
    )

    assert s.largestBSTSubtree(root) == 3

    print("all tests passed")

run_tests()

Test meaning: