1373. Maximum Sum BST in Binary Tree

Problem Description

The problem is about finding the maximum sum of all keys within any subtree of a binary tree, with the constraint that the subtree must also be a Binary Search Tree (BST). The definition of a BST here is:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees themselves must also be BSTs.

Our goal is to identify such subtrees that are BSTs within the larger binary tree and calculate their sums, finally returning the maximum one.

Intuition

To find the solution, we adopt a recursive approach that performs a depth-first search (DFS) on the binary tree. Here's the intuition behind the solution:

• Recursive DFS with BST validation: At each node, we perform a DFS to recursively validate whether the left and right subtrees are BSTs and to calculate their respective sums, along with the minimum and maximum values within those subtrees.

• Using tuple as return value: Each recursive call returns a tuple with details about the subtree:

  1. A boolean indicating whether the subtree is a BST.
  2. The minimum value within the subtree (for BST validation).
  3. The maximum value within the subtree (for BST validation).
  4. The sum of the keys of nodes within the subtree.

• Local and global results: Within each recursion, we maintain a local sum of the subtree if it's a valid BST. We also maintain a global variable ans to track the maximum sum encountered among all BST subtrees.

• Validating and updating BST properties: If the left and right subtrees of a given node are BSTs and the maximum key in the left is less than the current node's key while the current node's key is less than the minimum key in the right, the tree rooted at the current node is a BST. We then update the sum and the boundary values (minimum and maximum keys) for this subtree.

• Base case and invalid BST handling: When we reach a null child (a leaf node's child), we return a tuple that inherently suggests a valid empty BST with a sum of zero and safe boundary values. If a subtree is not a valid BST, we return a tuple that will fail the BST check for the parent call.

Throughout this process, we bubble up valid BST information while capturing their sum, and ensure the maximum sum found is updated in the global variable ans. Finally, we return ans as the result.

The provided implementation effectively traverses the tree while checking and validating the BST properties and computes the sum of the subtree keys until the maximum sum of any BST subtree within the overall tree is identified.

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

Solution Approach

The solution provided uses a Depth-First Search (DFS) approach to navigate through each node in the tree and applies the logic to identify valid BST subtrees and calculate their sums. The approach relies significantly on recursion and tuple unpacking. Below is a step-by-step explanation of the critical components of the reference solution:

• Data Structures: The primary data structure used here is the binary tree itself, traversed using recursion. The tuple is also used to return multiple values from the recursive calls.

• Base Case: When we encounter a None node, which is the case for a leaf node's child, we return a tuple (1, inf, -inf, 0) representing a valid BST with infinite boundaries (since a leaf node's child can be considered an empty BST) and a sum of 0.

• Recursive Case: For any non-null node, we perform the following:

  • Recursively call dfs(root.left) and dfs(root.right) to check the left and right subtrees, unpacking the returned tuple into lbst, lmi, lmx, ls for the left subtree and rbst, rmi, rmx, rs for the right subtree. Here:

    • lbst and rbst store whether the left and right subtrees are BSTs (1 for True, 0 for False).
    • lmi and rmi are the minimum values found in the left and right subtrees, respectively.
    • lmx and rmx are the maximum values found in the left and right subtrees, respectively.
    • ls and rs are the sum of all nodes in the left and right subtrees, respectively.

  • With the above information, we check whether the current node with its subtrees can form a valid BST. The conditions for this are:

    • The left and right subtrees must both be BSTs (lbst and rbst must be True).
    • The maximum value in the left subtree (lmx) must be less than the current node's value (root.val).
    • The current node's value must be less than the minimum value in the right subtree (rmi).

• Calculating Sum and Update Maximum Sum: If the current subtree rooted at root is a valid BST, we calculate the sum s by adding the node's value root.val to the sums of the left and right subtrees (ls + rs). We then use a global variable ans to track the maximum sum encountered, updating it with s if s is greater than ans. We also update the range of values (min and max) for the current subtree.

• Invalid BST Handling: If the current subtree rooted at root is not a valid BST, we return (0, 0, 0, 0) indicating the failure to meet BST requirements and providing non-useful boundary values and sum.

Finally, we initiate the recursion by calling dfs(root) and return the global maximum sum ans found among all valid BST subtrees in the binary tree.

The implementation efficiently ensures that each subtree is only traversed once and all necessary checks and calculations are performed during this single traversal. As a result, the algorithm is relatively efficient with a time complexity that is linearly proportional to the number of nodes in the tree.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the recursive Depth-First Search (DFS) with BST validation explained in the problem description.

Suppose we have the following binary tree:

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

We need to find the maximum sum of keys of any subtree that is also a Binary Search Tree (BST).

We start by calling the recursive function dfs() at the root node with the value 5.

1. Recursively call dfs() on the left child node 3.

   • For node 3, we call dfs() on its left child 2:
     • Node 2 is a leaf, so dfs(2) returns (1, 2, 2, 2) (it's a valid BST with itself being the only node, min = 2, max = 2, sum = 2).
   • Next, we call dfs() on the right child 4 of node 3:
     • Node 4 is also a leaf, so dfs(4) returns (1, 4, 4, 4).
   • Since both children of node 3 are valid BSTs and their max/min values respectively satisfy the BST properties, node 3 with its children is also a valid BST.
   • The sum for the subtree rooted at 3 is 3 (node value) + 2 (left sum) + 4 (right sum) = 9, so the function returns (1, 2, 4, 9) for node 3.

2. Next, we call dfs() on the right child node 8.

   • Node 8 has a right child 7. Since 7 is a leaf node, dfs(7) returns (1, 7, 7, 7).
   • Node 8 has no left child, so the left call returns (1, inf, -inf, 0), indicating an empty tree which is trivially a BST.
   • Since the left "empty subtree" and the right subtree rooted at 7 are valid BSTs and their max/min values respectively satisfy the BST properties with respect to node 8, the whole subtree rooted at 8 is a BST.
   • The sum for the subtree rooted at 8 is 8 (node value) + 0 (left sum) + 7 (right sum) = 15, and the function returns (1, -inf, 7, 15) for node 8.

3. With the results from dfs(3) and dfs(8), we now decide if the whole tree rooted at 5 is a BST.

   • We see that the values satisfy the BST properties because 4 < 5 < inf.
   • The sum of keys of this whole subtree is 5 (node value) + 9 (left sum) + 15 (right sum) = 29.
   • Hence, dfs(5) would return (1, 2, 7, 29).

Among all the subtrees we checked, the one with the maximum sum is the whole tree itself with a sum of 29. Therefore, the function dfs() initiated on the root 5 ultimately returns a maximum sum ans of 29, which is the result that will be returned by our algorithm.

This example illustrates the process of recursively exploring the tree, validating BST properties at each node, and combining sums to find the maximum BST subtree sum.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the tree. The code performs a single post-order traversal of the tree, visiting each node exactly once. During each visit, the function calculates and returns a tuple containing information about whether the subtree is a Binary Search Tree, the minimum and maximum values in the subtree, and the sum of values in the subtree if it is a BST. Since these operations are all done in constant time for each node, the time complexity of the entire algorithm is linear in the number of nodes.

The space complexity of the solution is also O(n) in the worst case. The worst-case space complexity occurs when the tree is skewed (having only left children or only right children), which results in a recursion depth equal to the number of nodes in the tree. Thus, the system call stack will at most have n activation records corresponding to the recursive calls. In a balanced tree, the space complexity would be O(log n) due to the height of the call stack corresponding to the tree height, but since we have to account for the worst case, we present the space complexity as O(n).

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