333. Largest BST Subtree

Problem Description

The problem asks to find the largest Binary Search Tree (BST) within a given binary tree. A largest BST here refers to a BST with the maximum number of nodes. It's important to remember that a binary tree is not necessarily a BST. A BST is a specific type of binary tree where the left subtree contains only nodes with values less than the root's value, and the right subtree only nodes with values greater than the root's value. Each subtree must also follow these rules.

In this context, a "subtree" is considered any node and all its descendants, and we need to identify the largest one that fulfills the constraints of a BST within the original binary tree. The solution should return the number of nodes contained in this largest BST.

Intuition

This problem can be efficiently solved using a recursive depth-first search (DFS). The intuition is that for a subtree to be a BST, both its left and right children must also be BSTs, and the value of all nodes in the left subtree must be less than the root's value, and those in the right subtree must be greater.

The solution leverages a helper function, typically dfs(root), which performs the following tasks:

• It checks the validity of BST for each node.
• It keeps track of the number of nodes in the valid subtree.
• It keeps track of the maximum and minimum value within the subtree to easily compare with its parent.

This recursive function returns a tuple (min_value, max_value, number_of_nodes) for each subtree analyzed. If the current subtree does not form a valid BST when considering its parent, it returns values that will cause the parent to also be invalid as a BST. This way, one does not need to further check subtrees of an already invalid BST, optimizing the process.

A key point for optimizing this algorithm is the early return when an invalid BST is found. Instead of checking all subtrees, the function stops early when it finds that the current subtree cannot possibly be a BST. This reduces the number of unnecessary checks and, therefore, the overall time complexity of the algorithm.

By maintaining a global or nonlocal variable that keeps track of the size of the largest BST found so far (ans in this case), we can keep updating the size whenever we find a larger valid BST.

At the end, the variable ans will hold the size of the largest found BST subtree, which we can return as the solution.

Learn more about Tree, Depth-First Search, Binary Search Tree, Dynamic Programming and Binary Tree patterns.

Solution Approach

The solution approach to finding the largest BST in a binary tree involves implementing a recursive Depth-First Search (DFS) that traverses the tree while performing checks and computations that ultimately reveal the largest BST subtree.

Here's a step-by-step breakdown of the dfs(root) function and how it integrates within the solution:

• A recursion base case is set. When the function encounters a None node (indicating an empty subtree), it returns (inf, -inf, 0). This ensures that an empty subtree will not affect the validity of its parent.

• The dfs function is called recursively on the left child dfs(root.left) and the right child dfs(root.right) of the current root. Each call will return the minimum value, maximum value, and node count of the valid BST subtree rooted at that child.

• These values are used to determine if the current root with its subtrees can form a valid BST:

  • The maximum value in the left subtree (lmx) must be less than root.val.
  • The minimum value in the right subtree (rmi) must be greater than root.val.

• When the current node's value respects the BST property in relation to its children's values, the current subtree rooted at root is a valid BST. The node count is the sum of the node counts from the left and right subtrees plus one (the current root node).

• The global variable ans is updated with the maximum value between its current value and the newly found BST's node count.

• The function returns a tuple containing the new minimum value, maximum value, and the total node count of the valid BST. The minimum and maximum values are updated to ensure the parent node will be able to verify its BST properties correctly.

• If the current subtree does not form a valid BST, the function returns (-inf, inf, 0) to indicate an invalid subtree.

• Once the entire tree has been traversed, the accumulated value of ans will represent the largest number of nodes found in a BST within the tree.

The code uses Python's nonlocal keyword to modify the ans variable defined outside of the nested dfs function, which simplifies updating the count of the largest BST found during the recursive traversal.

In terms of data structures, the algorithm primarily operates on the binary tree itself and uses tuples to store and pass around multiple values compactly. The recursion stack implicitly created by the recursive calls is a critical part of the DFS traversal pattern applied here.

By systematically exploring each node and determining locally whether a valid BST exists at that node, then combining those local decisions to inform the parent node's validity, this approach effectively breaks down the problem into manageable subproblems adhering to the "divide and conquer" strategy, which is common in recursive algorithms.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose you have the following binary tree:

1       10
2      /  \
3     5   15
4    / \   \
5   1   8   7

Each node contains a value, and we aim to find the largest BST within this binary tree.

1. We start with a DFS on the root node (10). We use the dfs function, which will return the minimum value, maximum value, and node count of the valid BST subtree.

2. We call dfs recursively on the left child (5) and right child (15).

3. For node 5, we call dfs recursively on node 1 (left child) and node 8 (right child).

   • Node 1 returns (1, 1, 1) because it has no children and is a valid BST on its own.
   • Node 8 returns (8, 8, 1) for the same reason.
   • Since the maximum value from the left (1) is less than 5, and the minimum value from the right (8) is greater than 5, node 5 with its children is a valid BST. We return (1, 8, 3) for node 5.

4. For node 15, we don't have a left child, and the right child is node 7.

   • Since 15 has no left child, we receive (inf, -inf, 0) from the left.
   • Node 7 returns (7, 7, 1) because it's a leaf node and hence a valid BST.
   • However, the minimum value from the right (7) is not greater than 15, so node 15 with its children cannot form a BST. Therefore, we return (-inf, inf, 0) for node 15, indicating it's an invalid subtree.

5. Now, back at the root node 10, we use the results from its children to determine whether it can form a BST. The left child returned (1, 8, 3) and the right child (-inf, inf, 0).

   • The maximum value from the left (8) is less than 10, but we cannot use the results from the right child because it's invalid.
   • So, node 10 and its entire tree cannot form a valid BST. We return (-inf, inf, 0) for node 10.

6. With these recursive calls, we maintain a global variable ans that is updated every time a valid subtree BST is found. In our case, the largest BST is the subtree rooted at node 5 with 3 nodes.

7. Once we have completed the recursive DFS traversal, the accumulated value of ans will hold the size of the largest BST found within the binary tree, which is 3 in this example. We return this value as the solution to the problem.

Solution Implementation

Time and Space Complexity

The given code defines a function largestBSTSubtree that finds the size of the largest BST (Binary Search Tree) within a binary tree. Let's analyze its time and space complexity.

Time Complexity

The main computation in the code is done by the dfs (Depth-First Search) function, which is a recursive function that is called on every node of the tree exactly once. At each node, dfs performs a constant amount of work. It checks if the current subtree is a BST, and updates the minimum and maximum value seen so far along with the count of nodes in the subtree.

Thus, for a binary tree with n nodes, every node is visited once, resulting in a time complexity of O(n).

Space Complexity

The space complexity of the code comes from two parts: the recursion stack and the nonlocal variable ans.

1. Recursion Stack: In the worst case, the recursion goes as deep as the height of the tree. For a balanced binary tree, the height is log(n), leading to a space complexity of O(log(n)) because of the recursion stack. However, in the worst case (a degenerate tree where each node has only one child), the height of the tree becomes n, which would result in a space complexity of O(n) for the recursion stack.

2. Nonlocal Variable: The nonlocal variable ans is used to track the maximum size of the BST found at any node. This only uses a constant amount of space, O(1).

The overall space complexity is then the maximum space required by any part of the algorithm. Thus, the space complexity of the algorithm is O(h) where h is the height of the tree. In the worst case, this simplifies to O(n).

Learn more about how to find time and space complexity quickly using problem constraints.