LeetCode 333: Largest BST Subtree Solution in Python – A Step-by-Step Guide

What Is LeetCode 333: Largest BST Subtree?

In LeetCode 333: Largest BST Subtree, you’re given the root of a binary tree, and your task is to return the size (number of nodes) of the largest subtree that is a valid BST. A BST requires all nodes in the left subtree to be less than the root, and all in the right to be greater. For example, in a tree 10->5->15->1->8->null->7, the largest BST is the subtree rooted at 5 (size 3: 5->1->8). This problem tests your ability to validate BST properties recursively, connecting to concepts in LeetCode 98: Validate Binary Search Tree.

Problem Statement

• Input: Root of a binary tree.
• Output: An integer—the size of the largest BST subtree.
• Rules:
• BST: Left subtree < root < right subtree.
• Subtree must include all descendants if valid.
• Size = number of nodes.

Constraints

• Number of nodes: 0 to 10⁴
• -10⁴ <= Node.val <= 10⁴

Examples

• Input: 10->5->15->1->8->null->7
• Output: 3 (Subtree: 5->1->8)
• Input: 1->4->3->2->4->null->5->6
• Output: 1 (No valid BST larger than a single node)
• Input: null
• Output: 0 (Empty tree)

Understanding the Problem: Finding the Largest BST

To solve LeetCode 333: Largest BST Subtree in Python, we need to identify the largest subtree within the given binary tree that satisfies BST properties. A naive approach—checking every subtree with a full BST validation—is O(n²), too slow for 10⁴ nodes. Instead, we’ll use:

• Best Solution (Bottom-Up DFS): O(n) time, O(h) space—fast and scalable (h = tree height).
• Alternative Solution (Top-Down): O(n²) time, O(h) space—clear but inefficient.

Let’s start with the bottom-up DFS solution, explained in a beginner-friendly way.

Best Solution: Bottom-Up DFS

Why This Is the Best Solution

The bottom-up DFS approach is the top choice for LeetCode 333 because it’s efficient—O(n) time, O(h) space—and validates BST properties while computing sizes in a single pass. It uses a post-order traversal to check subtrees and propagate results upward, tracking min/max values and sizes. It’s like inspecting the forest from the leaves up—smart and thorough!

How It Works

Think of this as a tree inspector:

• Step 1: DFS Post-Order:
• For each node, process left and right subtrees first.
• Step 2: Return Tuple:
• (is_bst, size, min_val, max_val) for each subtree.
• Leaf: (True, 1, val, val).
• Step 3: Validate and Combine:
• Check if current node forms a BST with children.
• Update max size if valid.
• Step 4: Why It Works:
• Bottom-up ensures all subtrees are validated.
• Single pass avoids redundant checks.

It’s like building a BST report from the ground up!

Step-by-Step Example

Example: 10->5->15->1->8->null->7

• DFS(1): (True, 1, 1, 1)
• DFS(8): (True, 1, 8, 8)
• DFS(5): Left=(T,1,1,1), Right=(T,1,8,8), 5>1, 5<8 → (True, 3, 1, 8)
• DFS(7): (True, 1, 7, 7)
• DFS(15): Right=(T,1,7,7), 15>7 → (False, 1, 7, 15)
• DFS(10): Left=(T,3,1,8), Right=(F,1,7,15), 10>8, 10<7 → (False, 3, 1, 15)
• Result: Max size = 3 (at node 5)

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        # Global max size
        self.max_size = 0

        def dfs(node):
            if not node:
                return (True, 0, float('inf'), float('-inf'))
            if not node.left and not node.right:
                self.max_size = max(self.max_size, 1)
                return (True, 1, node.val, node.val)

            # Process children
            left = dfs(node.left)
            right = dfs(node.right)

            # Check if current subtree is BST
            if (left[0] and right[0] and 
                left[3] < node.val < right[2]):
                size = left[1] + right[1] + 1
                self.max_size = max(self.max_size, size)
                min_val = min(node.val, left[2])
                max_val = max(node.val, right[3])
                return (True, size, min_val, max_val)
            else:
                return (False, 0, 0, 0)  # Size irrelevant if not BST

        dfs(root)
        return self.max_size

• Line 3: Track global max size.
• Lines 6-11: Base cases: null or leaf nodes.
• Lines 14-24: DFS:
• Recurse on children.
• Validate BST: left max < node < right min.
• Compute size, update max_size if valid.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h = height).

This is like a BST-hunting explorer—fast and precise!

Alternative Solution: Top-Down Validation

Why an Alternative Approach?

The top-down approach—O(n²) time, O(h) space—validates each subtree as a BST from the root down, counting nodes if valid. It’s more intuitive for understanding BST checks but slower due to repeated validations. It’s like inspecting the forest from the top—clear but heavy!

How It Works

Check from top:

• Step 1: For each node, validate subtree as BST.
• Step 2: Count nodes if valid.
• Step 3: Track max size across all subtrees.

Step-by-Step Example

Example: 5->3->6->2->4

• Root 5: Left=3(T), Right=6(F) → Size=1
• Node 3: Left=2(T), Right=4(T), 3>2, 3<4 → Size=3
• Node 6: No children → Size=1
• Result: Max size = 3

Code for Top-Down Approach

Copy codeclass Solution:
    def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
        def is_bst(node, min_val, max_val):
            if not node:
                return True
            if node.val <= min_val or node.val >= max_val:
                return False
            return (is_bst(node.left, min_val, node.val) and 
                    is_bst(node.right, node.val, max_val))

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

        def find_largest(node):
            if not node:
                return 0
            if is_bst(node, float('-inf'), float('inf')):
                return count_nodes(node)
            return max(find_largest(node.left), find_largest(node.right))

        return find_largest(root)

• Time Complexity: O(n²)—validate BST per node.
• Space Complexity: O(h)—recursion stack.

It’s a top-down BST checker—vivid but slow!

Comparing the Two Solutions

• Bottom-Up DFS (Best):
• Pros: O(n) time, O(h) space, single pass.
• Cons: Recursive tuple logic.
• Top-Down (Alternative):
• Pros: O(n²) time, O(h) space, intuitive validation.
• Cons: Much slower.

Bottom-up wins for efficiency.

Additional Examples and Edge Cases

• [1]: 1.
• [2->1]: 2.
• []: 0.

Both handle these, but bottom-up is faster.

Complexity Breakdown

• Bottom-Up DFS: Time O(n), Space O(h).
• Top-Down: Time O(n²), Space O(h).

Bottom-up is the clear choice.

Key Takeaways

• Bottom-Up DFS: Build from leaves—efficient!
• Top-Down: Check from root—clear!
• Python: Trees and recursion shine—see [Python Basics](/python/basics).
• BSTs: Subtrees hold the key.

Final Thoughts: Find the BST Gem

LeetCode 333: Largest BST Subtree in Python is a tree-traversal treasure hunt. The bottom-up DFS solution offers speed and elegance, while top-down provides a straightforward baseline. Want more tree challenges? Try LeetCode 98: Validate Binary Search Tree or LeetCode 450: Delete Node in a BST. Ready to explore? Head to Solve LeetCode 333 on LeetCode (premium) and uncover that largest BST today!