Problem Description

You are given the root of a binary tree. Your task is to find the largest subtree that is also a valid Binary Search Tree (BST). The "largest" subtree means the one with the most number of nodes.

A Binary Search Tree must satisfy these properties:

• All values in the left subtree of any node must be less than that node's value
• All values in the right subtree of any node must be greater than that node's value
• These properties must hold for every node in the BST

A subtree must include all of its descendants - you cannot pick and choose nodes; if you include a node, you must include all nodes below it.

For example, if you have a binary tree where only a portion forms a valid BST, you need to identify that valid BST portion and count its nodes. The answer should be the count of nodes in the largest such valid BST subtree found anywhere in the given tree.

The solution uses a post-order traversal approach where for each node, it:

1. Checks if the left and right subtrees are valid BSTs
2. Verifies if the current node can form a larger BST with its subtrees by checking if max(left subtree) < node.val < min(right subtree)
3. Returns the minimum value, maximum value, and size of the BST rooted at the current node
4. Uses infinity values (inf and -inf) as markers to indicate invalid BSTs

The function returns three values for each node:

• Minimum value in the subtree
• Maximum value in the subtree
• Number of nodes if it's a valid BST (0 if invalid)

The variable ans keeps track of the maximum BST size found during the traversal.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: Although it's specifically a binary tree, a tree is a special type of graph (connected acyclic graph). The problem involves nodes with parent-child relationships.

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to find the largest BST subtree.

DFS

• We arrive at DFS: For tree problems, DFS is the natural choice. We need to traverse the entire tree to examine each potential subtree and determine if it's a valid BST.

Why DFS is the right approach:

• We need to validate BST properties at each node, which requires information from both left and right subtrees
• Post-order traversal (a form of DFS) allows us to process children before parents, gathering necessary information about subtree validity and bounds
• Each node needs to know the min/max values and validity status of its subtrees to determine if it can form a larger BST

Conclusion: The flowchart correctly leads us to use DFS for this tree-based problem. The solution implements a post-order DFS traversal where each recursive call returns three pieces of information (min value, max value, and node count) to help parent nodes determine if they can form valid BSTs with their subtrees.

Intuition

When we need to find the largest BST subtree, we face a key challenge: how do we efficiently check if each subtree is a valid BST while also tracking its size?

The natural instinct might be to check each node as a potential root and validate if its entire subtree forms a BST. However, this would involve repeated traversals and redundant work.

Instead, let's think bottom-up. If we process the tree from the leaves upward, we can build our answer incrementally. For each node, we need to answer three questions:

1. Are my left and right subtrees valid BSTs?
2. Can I form a larger BST by including myself with my subtrees?
3. What information should I pass to my parent?

The key insight is that for a node to form a valid BST with its subtrees, we need to ensure that:

• All values in the left subtree are less than the current node's value
• All values in the right subtree are greater than the current node's value

Rather than checking every single node in the subtrees, we only need to know the maximum value from the left subtree and the minimum value from the right subtree. If max(left) < node.val < min(right), then combining these subtrees with the current node creates a valid BST.

This leads us to track three pieces of information for each subtree:

• The minimum value in the subtree (to help parent nodes validate BST property)
• The maximum value in the subtree (to help parent nodes validate BST property)
• The size of the valid BST (0 if the subtree is not a valid BST)

By using impossible values like inf and -inf as sentinel values when a subtree isn't a valid BST, we create a clever mechanism where invalid subtrees automatically fail the BST check at their parent level (since no real value can be greater than inf or less than -inf).

This bottom-up approach ensures we visit each node exactly once while maintaining all necessary information to solve the problem efficiently.

Solution Approach

The solution implements a post-order DFS traversal using a recursive helper function dfs that processes each node in the tree.

Core Implementation Details:

The dfs function returns a tuple of three values for each node:

• min_val: The minimum value in the subtree
• max_val: The maximum value in the subtree
• size: The number of nodes if it's a valid BST, 0 otherwise

Base Case: When we encounter a None node (empty subtree), we return (inf, -inf, 0). This clever choice ensures that:

• An empty left subtree has max = -inf, which is always less than any parent node value
• An empty right subtree has min = inf, which is always greater than any parent node value
• The size is 0 since there are no nodes

Recursive Processing: For each non-null node, we:

1. Recursively process the left subtree: lmi, lmx, ln = dfs(root.left)
2. Recursively process the right subtree: rmi, rmx, rn = dfs(root.right)

BST Validation: We check if the current node can form a valid BST with its subtrees using the condition:

if lmx < root.val < rmi:

This verifies that:

• The maximum value in the left subtree (lmx) is less than the current node's value
• The minimum value in the right subtree (rmi) is greater than the current node's value

When a Valid BST is Found: If the BST property is satisfied:

1. Update the global answer: ans = max(ans, ln + rn + 1) where the size is left subtree nodes + right subtree nodes + current node
2. Return the updated bounds and size for the parent's validation:
   • New minimum: min(lmi, root.val) - either the left subtree's minimum or current node value
   • New maximum: max(rmx, root.val) - either the right subtree's maximum or current node value
   • Total size: ln + rn + 1

When BST Property Fails: If the current subtree is not a valid BST, return (-inf, inf, 0). These sentinel values ensure that:

• Any parent node trying to form a BST with this invalid subtree will fail the validation check
• No real node value can satisfy inf < node.val < -inf

Global Answer Tracking: The variable ans is initialized to 0 and updated whenever we find a valid BST, keeping track of the maximum size encountered throughout the traversal.

The algorithm visits each node exactly once, making it O(n) in time complexity, where n is the number of nodes in the tree.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Consider this binary tree:

        10
       /  \
      5    15
     / \     \
    1   8    20

We'll trace through the post-order traversal and see how the algorithm identifies the largest BST subtree.

Step 1: Process leaf node 1

• dfs(1) is called
• Left child is None: returns (inf, -inf, 0)
• Right child is None: returns (inf, -inf, 0)
• Check BST property: -inf < 1 < inf ✓ (valid)
• Return: (1, 1, 1) - min=1, max=1, size=1
• Update global ans = 1

Step 2: Process leaf node 8

• Similar to node 1
• Return: (8, 8, 1) - min=8, max=8, size=1
• Global ans remains 1

Step 3: Process node 5

• Left subtree (node 1): (1, 1, 1)
• Right subtree (node 8): (8, 8, 1)
• Check BST property: 1 < 5 < 8 ✓ (valid)
• This forms a valid BST with 3 nodes!
• Return: (1, 8, 3) - min=1, max=8, size=3
• Update global ans = 3

Step 4: Process leaf node 20

• Similar to other leaf nodes
• Return: (20, 20, 1) - min=20, max=20, size=1

Step 5: Process node 15

• Left child is None: returns (inf, -inf, 0)
• Right subtree (node 20): (20, 20, 1)
• Check BST property: -inf < 15 < 20 ✓ (valid)
• Return: (15, 20, 2) - min=15, max=20, size=2
• Global ans remains 3

Step 6: Process root node 10

• Left subtree (node 5): (1, 8, 3)
• Right subtree (node 15): (15, 20, 2)
• Check BST property: 8 < 10 < 15 ✓ (valid)
• The entire tree is a valid BST with 6 nodes!
• Return: (1, 20, 6) - min=1, max=20, size=6
• Update global ans = 6

Final Answer: 6

Now let's see what happens with an invalid BST. Consider this modified tree:

        10
       /  \
      5    15
     / \     \
    1   12   20

When we reach node 5:

• Left subtree (node 1): (1, 1, 1)
• Right subtree (node 12): (12, 12, 1)
• Check BST property: 1 < 5 < 12 ✗ (invalid - 12 > 5 but it's in the left subtree of 10)
• Actually wait, locally at node 5: 1 < 5 < 12 ✓ (this is valid!)
• Return: (1, 12, 3)

When we reach node 10:

• Left subtree (node 5): (1, 12, 3)
• Right subtree (node 15): (15, 20, 2)
• Check BST property: 12 < 10 < 15 ✗ (invalid - 12 > 10!)
• Return: (-inf, inf, 0) - marking this subtree as invalid
• The largest BST remains the subtree rooted at node 5 with size 3

This example demonstrates how the algorithm correctly identifies that while the subtree rooted at node 5 is a valid BST, the entire tree is not, because node 12 violates the BST property relative to the root node 10.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the number of nodes in the binary tree.

The algorithm performs a depth-first search (DFS) traversal of the tree, visiting each node exactly once. At each node, the function performs constant-time operations:

• Comparing values (lmx < root.val < rmi)
• Computing min/max values (min(lmi, root.val), max(rmx, root.val))
• Updating the answer variable
• Basic arithmetic operations (ln + rn + 1)

Since each node is visited once and only constant work is done per node, the overall time complexity is O(n).

Space Complexity: O(h) where h is the height of the binary tree.

The space complexity is determined by the recursive call stack. In the worst case:

• For a skewed tree (essentially a linked list), the height h = n, resulting in O(n) space complexity
• For a balanced tree, the height h = log(n), resulting in O(log n) space complexity

The algorithm doesn't use any additional data structures that scale with input size. Each recursive call only stores a constant amount of data (the return values and local variables), so the space complexity is proportional to the maximum depth of the recursion, which equals the height of the tree.

Common Pitfalls

1. Incorrectly Handling the Definition of "Subtree"

Pitfall: A common mistake is misunderstanding that a valid subtree must include ALL descendants of a node. Some developers might try to "skip" certain nodes to form a BST, which violates the problem constraints.

Example of incorrect thinking:

    10
   /  \
  5    15
 / \   /
1   8 7   # Node 7 violates BST property under 15

# WRONG: Trying to count nodes [1, 5, 8, 10, 15] by skipping node 7
# CORRECT: The largest valid BST is [1, 5, 8] with size 3

Solution: The post-order traversal approach naturally handles this by propagating invalid BST markers (-inf, inf, 0) up the tree whenever a violation is found, ensuring parent nodes cannot form a BST with invalid subtrees.

2. Confusing BST Validation Logic with Sentinel Values

Pitfall: The use of inf and -inf as sentinel values can be confusing. Developers might accidentally swap them or use them incorrectly.

Common mistakes:

# WRONG: Returning (inf, -inf, 0) for invalid BST
# This would make parent validation always succeed incorrectly

# WRONG: Returning (-inf, inf, 0) for empty node
# This would make all parent validations fail

Solution: Remember the logic:

• Empty node: Returns (inf, -inf, 0) - creates a "valid range" that any parent can work with
• Invalid BST: Returns (-inf, inf, 0) - creates an "impossible range" that fails any parent validation

3. Incorrect Range Calculation for Valid BST

Pitfall: When a valid BST is found, calculating the new min/max values incorrectly.

Wrong implementation:

if left_max < node.val < right_min:
    # WRONG: Using left_min and right_max directly
    return left_min, right_max, current_size  # Fails when subtree is empty!

Why it fails: When a subtree is empty, left_min = inf or right_max = -inf, which are sentinel values, not actual tree values.

Correct implementation:

if left_max < node.val < right_min:
    # CORRECT: Use min/max to handle empty subtree cases
    return min(left_min, node.val), max(right_max, node.val), current_size

4. Using Mutable Default Arguments or Global Variables Incorrectly

Pitfall: Using a list as default argument or improperly scoped variables:

Wrong approaches:

def largestBSTSubtree(self, root, ans=[0]):  # WRONG: Mutable default
    # This persists across multiple function calls!
  
def largestBSTSubtree(self, root):
    ans = 0  # Local variable
    def dfs(node):
        # WRONG: Can't modify 'ans' without nonlocal declaration
        ans = max(ans, current_size)  # UnboundLocalError!

Correct solutions:

# Option 1: Use instance variable
self.max_bst_size = 0

# Option 2: Use nonlocal declaration
def largestBSTSubtree(self, root):
    ans = 0
    def dfs(node):
        nonlocal ans
        ans = max(ans, current_size)
      
# Option 3: Pass and return the answer
def dfs(node, current_max):
    # ... calculate new_max ...
    return min_val, max_val, size, new_max

5. Not Handling Edge Cases Properly

Pitfall: Forgetting to handle special cases:

Edge cases to consider:

• Empty tree (root is None)
• Single node tree
• Tree where entire tree is a valid BST
• Tree where no valid BST exists (each node forms BST of size 1)

Solution: The algorithm handles these naturally:

# Empty tree
if root is None:
    return 0  # Add this check before calling dfs

# Single node - automatically handled as BST of size 1
# Full tree BST - checked at root level
# No valid BST - each node counted as size 1 BST