# 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: | Rule | Meaning | |---|---| | Left subtree | All values are smaller than the root | | Right subtree | All values are larger than the root | | Recursive property | Both left and right subtrees must also be BSTs | The subtree does not need to include the original root. Any connected subtree inside the tree may be the answer. ## Input and Output | Item | Meaning | |---|---| | Input | Root of a binary tree | | Output | Size of the largest BST subtree | | BST condition | Left values `< root <` right values | Function shape: ```python def largestBSTSubtree(root: Optional[TreeNode]) -> int: ... ``` ## Examples Example 1: ```text Input: 10 / \ 5 15 / \ \ 1 8 7 Output: 3 ``` The subtree: ```text 5 / \ 1 8 ``` is a valid BST of size `3`. The whole tree is not a BST because: ```text 7 < 15 ``` but `7` appears in the right subtree of `15`. So the answer is `3`. Example 2: ```text 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: ```text 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: | Value | Meaning | |---|---| | `is_bst` | Whether the subtree is a BST | | `size` | Size of the subtree if it is a BST | | `min_value` | Smallest value in the subtree | | `max_value` | Largest value in the subtree | Suppose we already know the information for the left subtree and the right subtree. The current subtree is a BST if: ```text left subtree is BST right subtree is BST left.max_value < current node value current node value < right.min_value ``` If true: ```text 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: ```text empty subtree is a valid BST ``` with: ```text size = 0 min_value = +infinity max_value = -infinity ``` These extreme values simplify comparisons. ## Walkthrough Use: ```text 10 / \ 5 15 / \ \ 1 8 7 ``` Start from leaves. Node `1`: ```text BST size = 1 min = 1 max = 1 ``` Node `8`: ```text BST size = 1 min = 8 max = 8 ``` Now process node `5`. Conditions: ```text 1 < 5 < 8 ``` So subtree rooted at `5` is a BST. Size: ```text 1 + 1 + 1 = 3 ``` Now process node `15`. Its right child is `7`. Condition: ```text 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: ```text 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: ```text 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 | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Every node is processed once | | Space | `O(h)` | DFS recursion stack, where `h` is tree height | In the worst case of a skewed tree: ```text h = n ``` ## Implementation ```python 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: ```python self.answer = 0 ``` The DFS returns: ```python (is_bst, size, min_value, max_value) ``` For a null node: ```python return True, 0, float("inf"), float("-inf") ``` This means: | Value | Meaning | |---|---| | `True` | Empty subtree is a BST | | `0` | No nodes | | `+inf` | Neutral minimum | | `-inf` | Neutral maximum | Then recursively process children: ```python 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: ```python left_max < node.val < right_min ``` If valid: ```python size = left_size + right_size + 1 ``` Update the global maximum: ```python self.answer = max(self.answer, size) ``` Return updated subtree information. If invalid: ```python return False, 0, 0, 0 ``` The exact values do not matter because ancestors will reject invalid subtrees immediately. ## Testing ```python 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: | Test | Why | |---|---| | Mixed valid/invalid tree | Standard example | | Full BST | Entire tree valid | | Single node | Minimum non-empty tree | | Invalid root but valid subtree | Largest BST not at root |