NUHMAN.com

Introduction

LeetCode 333: Largest BST Subtree is a binary tree problem that challenges you to find the largest Binary Search Tree (BST) subtree within a given binary tree. This problem helps improve your understanding of binary search trees, tree traversal, and recursion.

The task involves identifying the largest BST subtree within a binary tree and returning the size of this subtree.

Problem Statement

Given a binary tree, find the size of the largest subtree which is also a Binary Search Tree (BST).

A Binary Search Tree (BST) is a binary tree in which:

• The left subtree contains only nodes with values less than the node’s value.
• The right subtree contains only nodes with values greater than the node’s value.
• Both left and right subtrees must also be BSTs.

Example

python

Input: [10,5,15,1,8,null,7]
Output: 3
Explanation: The largest BST subtree is the one rooted at node 5, which has 3 nodes.

Input: [4,2,7,1,3,null,null]
Output: 2
Explanation: The largest BST subtree is the one rooted at node 2, which has 2 nodes.

✅ Approach: Postorder Traversal and Recursive Validation

The goal is to recursively check each subtree to determine if it is a valid BST. If it is, we calculate its size and update the result if it is the largest valid subtree seen so far. If a subtree is not a valid BST, we return a failure flag and avoid further exploration in that subtree.

Key Idea: Use postorder traversal to evaluate and update the largest BST subtree.

Steps:

1. Postorder Traversal: Traverse the tree from the leaves up. For each node:

• Check if the left and right subtrees are BSTs.
• Ensure the node value is greater than the maximum value in the left subtree and less than the minimum value in the right subtree.

1. Store Information: For each node, store:

• Whether its subtree is a BST.
• The size of the subtree.
• The minimum and maximum values in the subtree.

1. Return the Result: Track the size of the largest BST subtree.

✅ Python Code

python

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: TreeNode) -> int:
        def postorder(node):
            if not node:
                return (True, 0, float('inf'), float('-inf'))
            
            # Recurse on left and right children
            left_is_bst, left_size, left_min, left_max = postorder(node.left)
            right_is_bst, right_size, right_min, right_max = postorder(node.right)
            
            # Check if the current node forms a BST
            if left_is_bst and right_is_bst and node.val > left_max and node.val < right_min:
                # It forms a BST
                size = left_size + right_size + 1
                # Update the result with the largest BST size found so far
                self.max_size = max(self.max_size, size)
                # Return true, the size, and the new min/max values
                return (True, size, min(node.val, left_min), max(node.val, right_max))
            else:
                # If not a BST, return false and the size of the largest BST found
                return (False, 0, 0, 0)
        
        self.max_size = 0
        postorder(root)
        return self.max_size

🧪 Dry Run Example

Input: root = [10, 5, 15, 1, 8, null, 7]

1. Start at Root (10):

• Left subtree: 5 -> 1, 8 (BST)
• Right subtree: 15 -> 7 (Not a BST)
• The largest BST is rooted at node 5, with a size of 3.

1. Postorder Traversal:

• Visit left subtree (1, 8) → subtree sizes 1, 1 (BST).
• Visit right subtree (15 -> 7) → invalid, size 0.
• Update result with size 3.

Final result: 3.

⏱️ Time & Space Complexity

MetricValueTime ComplexityO(N)Space ComplexityO(H)

• N is the number of nodes in the tree.
• H is the height of the tree, which is the space required for recursion stack.

🧠 Key Takeaways

• Postorder traversal is used for bottom-up tree evaluation, which is key in checking if a subtree is a valid BST.
• The solution is based on recursive validation and dynamic programming to store subtree information, allowing for efficient calculation of the largest BST.
• Min/Max values are used to check if the current node satisfies the BST properties.

🧱 Edge Cases

• Empty tree → return 0.
• Tree where every node is part of a valid BST → return the size of the entire tree.
• Single-node tree → return 1.

✅ Conclusion

LeetCode 333: Largest BST Subtree is an excellent problem for learning how to combine tree traversal with dynamic programming. The use of postorder traversal and storing the minimum and maximum values of each subtree makes this solution efficient and elegant. By solving this problem, you gain a deeper understanding of tree structures and recursive algorithms.