#1373

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Maximum Sum BST in Binary Tree

Find the maximum sum of values from any Binary Search Tree (BST) subtree in a binary tree.

dynamic programming tree depth first search binary search tree binary tree

Problem Statement

Given a binary tree, you need to find the maximum sum of the values of any subtree that is also a Binary Search Tree (BST). A Binary Search Tree is defined as a tree where for each node, the left child is smaller than the node, and the right child is greater than the node.

You must return the sum of the largest BST subtree. If there are no BST subtrees, the sum should be 0. The solution requires an efficient approach that tracks the validity of BSTs within the tree and computes their sum.

Examples

Example 1

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]

Output: 20

Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2

Input: root = [4,3,null,1,2]

Output: 2

Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Example 3

Input: root = [-4,-2,-5]

Output: 0

All values are negatives. Return an empty BST.

Constraints

The number of nodes in the tree is in the range [1, 4 * 104].
-4 * 104 <= Node.val <= 4 * 104

Solution Approach

Depth-First Search (DFS) Traversal

Perform a DFS to explore every subtree in the binary tree. For each node, check if the subtree rooted at that node is a valid BST and compute its sum. Use a helper function that returns multiple parameters: the sum, whether it's a valid BST, and the minimum and maximum values of the subtree.

State Tracking with Helper Structure

During DFS, track the state of each node using a structure with four parameters: the sum of the BST, a boolean indicating if the subtree is a BST, the maximum value in the left subtree, and the minimum value in the right subtree. This helps efficiently check if the subtree is a valid BST and calculate the sum in one pass.

Return Maximum Valid BST Sum

As you traverse, update the maximum sum encountered for valid BSTs. If a subtree is not a valid BST, discard it. At the end of the traversal, return the largest BST sum found.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution is O(n) where n is the number of nodes in the tree, as each node is visited once during the DFS. The space complexity is O(h), where h is the height of the tree, for the recursion stack used in DFS.

What Interviewers Usually Probe

Look for understanding of tree traversal and state tracking during DFS.
Assess the candidate's ability to manage multiple parameters (sum, validity, min, max) during traversal.
Check if the candidate optimizes the solution by avoiding unnecessary recalculations.

Common Pitfalls or Variants

Common pitfalls

Failing to track the minimum and maximum values of subtrees can lead to incorrect validation of the BST.
Not considering the case where no valid BST exists and returning an incorrect sum.
Inefficient or incorrect recursive calls can lead to excessive time complexity, especially in large trees.

Follow-up variants

Consider adding additional constraints like limiting the maximum tree depth to test efficiency.
Adapt the problem for trees that contain duplicate values and check how BST validation is handled.
Extend the problem to consider the maximum sum for subtrees with specific node value constraints.

FAQ

How does Binary Search Tree validation work in this problem?

A valid BST is determined by ensuring that all values in the left subtree are smaller than the root node, and all values in the right subtree are greater. The algorithm tracks this using the minimum and maximum values of the subtrees.

What happens if there are no valid BSTs in the tree?

If there are no valid BST subtrees, the solution should return 0, indicating that no valid BST sum exists.

How do I handle nodes with duplicate values in this problem?

In this problem, duplicate values are not allowed in a BST. If duplicates are present, the subtree rooted at that node would not be a valid BST.

How can I optimize my solution for larger trees?

To optimize your solution, make sure you only traverse each node once and avoid recalculating results for the same subtrees. This can be achieved by tracking subtree information during the DFS pass.

What is the importance of the four parameters used in the helper structure?

The four parameters—sum, isBST, maxLeft, and minRight—help in determining if a subtree is a valid BST and calculating its sum, ensuring that you can check the validity and compute the sum in a single traversal.

terminal

Solution

Solution 1: DFS

To determine whether a tree is a binary search tree, it needs to meet the following four conditions:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

# 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 maxSumBST(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> tuple:
            if root is None:
                return 1, inf, -inf, 0
            lbst, lmi, lmx, ls = dfs(root.left)
            rbst, rmi, rmx, rs = dfs(root.right)
            if lbst and rbst and lmx < root.val < rmi:
                nonlocal ans
                s = ls + rs + root.val
                ans = max(ans, s)
                return 1, min(lmi, root.val), max(rmx, root.val), s
            return 0, 0, 0, 0

        ans = 0
        dfs(root)
        return ans

Continue Practicing

#1372 longest zigzag path in a binary tree #1382 balance a binary search tree #1305 all elements in two binary search trees