LeetCode 1373 - Maximum Sum BST in Binary Tree

LeetCode Problem 1373

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

This problem asks us to examine every possible subtree inside a binary tree and determine whether that subtree forms a valid Binary Search Tree, abbreviated as BST. Among all valid BST subtrees, we must return the maximum possible sum of node values.

A subtree consists of a node together with all of its descendants. Every node in the tree can potentially be the root of a subtree, so we must evaluate many overlapping regions of the tree.

A Binary Search Tree follows three rules:

1. Every value in the left subtree must be strictly smaller than the current node's value.
2. Every value in the right subtree must be strictly greater than the current node's value.
3. Both left and right subtrees must themselves also be BSTs.

The input is the root node of a binary tree. The tree is not guaranteed to be a BST overall. Some parts of the tree may satisfy BST rules while others do not.

The output is the largest sum of values among all valid BST subtrees. If all values are negative, we are allowed to choose the empty BST, whose sum is considered 0.

The constraints are important:

• The tree may contain up to 4 * 10^4 nodes.
• Node values range from -4 * 10^4 to 4 * 10^4.

These limits immediately rule out inefficient repeated traversals. An O(n^2) solution would be too slow for 40,000 nodes. We need a solution that processes each node efficiently, ideally once.

Several edge cases are especially important:

• The entire tree may already be a valid BST.
• No subtree larger than one node may form a BST.
• All node values may be negative, requiring us to return 0.
• A subtree may fail BST rules because of a deep descendant, not just direct children.
• Duplicate values invalidate BST conditions because the rules require strict inequality.

Approaches

Brute Force Approach

A straightforward approach is to examine every subtree independently.

For each node in the tree:

1. Treat that node as the root of a subtree.
2. Check whether the subtree is a valid BST.
3. If it is valid, compute the sum of all nodes in that subtree.
4. Track the maximum sum seen so far.

To validate a BST correctly, we would need to ensure that all descendants satisfy valid lower and upper bounds. This usually requires a full traversal of the subtree.

Similarly, computing the subtree sum also requires traversing all nodes in that subtree.

Since there are n possible subtree roots and each validation may cost O(n) in the worst case, the total complexity becomes O(n^2).

With up to 40,000 nodes, this approach is far too slow.

Optimal Approach

The key observation is that BST validation and subtree sum computation can both be performed during a single postorder traversal.

A node can form a valid BST only if:

• Its left subtree is a BST.
• Its right subtree is a BST.
• The maximum value in the left subtree is smaller than the current node value.
• The minimum value in the right subtree is greater than the current node value.

This means each node depends on information from its children.

A postorder traversal is ideal because it processes children before the parent. By the time we evaluate a node, we already know everything about its left and right subtrees.

For every subtree, we return four pieces of information:

• Whether the subtree is a valid BST.
• The minimum value inside the subtree.
• The maximum value inside the subtree.
• The sum of all nodes in the subtree.

Using this information, the parent can determine whether combining the two child subtrees with the current node still forms a valid BST.

Each node is processed exactly once, giving an O(n) solution.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(h)	Repeatedly validates and sums subtrees
Optimal	O(n)	O(h)	Single postorder DFS traversal

Here, h is the height of the tree.

Algorithm Walkthrough

1. Perform a postorder DFS traversal.

We process the left subtree first, then the right subtree, and finally the current node. This order ensures that when evaluating a node, we already know whether its children form valid BSTs. 2. Define the information returned by DFS.

For every subtree, return:

• is_bst, whether the subtree is a valid BST
• min_value, smallest value in the subtree
• max_value, largest value in the subtree
• subtree_sum, total sum of the subtree

3. Handle the base case.

An empty subtree is considered a valid BST.

For a null node:

• is_bst = True
• min_value = +infinity
• max_value = -infinity
• subtree_sum = 0

Using infinities makes comparisons easy when evaluating parent nodes. 4. Recursively process the left and right children.

The DFS call returns the four values for both child subtrees. 5. Determine whether the current subtree is a BST.

The subtree rooted at the current node is valid only if:

• Left subtree is a BST
• Right subtree is a BST
• left_max < node.val < right_min

6. Compute the subtree sum if valid.

If the subtree forms a BST:

total_sum = left_sum + right_sum + node.val

Update the global maximum answer with this sum. 7. Compute subtree boundaries.

The minimum value becomes:

min(left_min, node.val)

The maximum value becomes:

max(right_max, node.val)

8. Handle invalid BSTs.

If the subtree is invalid, return False for is_bst.

The remaining values do not matter because invalid BSTs cannot contribute to larger valid BSTs. 9. Continue until traversal completes.

The global maximum stores the largest BST subtree sum found anywhere in the tree.

Why it works

The algorithm works because every BST condition for a parent depends entirely on properties of its left and right subtrees. By processing children before parents, we always have complete information available when evaluating a node.

The returned (is_bst, min_value, max_value, subtree_sum) tuple acts as a compact summary of each subtree. This summary contains exactly the information needed for the parent to verify BST validity and compute sums correctly.

Since every node is processed once and every subtree is evaluated exactly once, the algorithm is both correct and efficient.

Python Solution

# 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

from typing import Optional
import math

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.best_sum = 0

        def dfs(node: Optional[TreeNode]):
            if not node:
                return True, math.inf, -math.inf, 0

            left_is_bst, left_min, left_max, left_sum = dfs(node.left)
            right_is_bst, right_min, right_max, right_sum = dfs(node.right)

            if (
                left_is_bst
                and right_is_bst
                and left_max < node.val < right_min
            ):
                current_sum = left_sum + right_sum + node.val

                self.best_sum = max(self.best_sum, current_sum)

                current_min = min(left_min, node.val)
                current_max = max(right_max, node.val)

                return True, current_min, current_max, current_sum

            return False, 0, 0, 0

        dfs(root)

        return self.best_sum

The implementation follows the postorder traversal strategy directly.

The dfs() function returns four values describing the subtree rooted at the current node. The recursive calls first gather information from the left and right children.

The BST condition is checked using:

left_max < node.val < right_min

This guarantees that all values in the left subtree are smaller and all values in the right subtree are larger.

If the subtree is valid, the code computes the total subtree sum and updates the global maximum.

The use of math.inf and -math.inf simplifies comparisons for empty subtrees. For example, a leaf node automatically satisfies BST conditions because:

-inf < node.val < inf

Invalid subtrees return False, preventing them from being incorrectly combined into larger BSTs.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

import "math"

type Result struct {
	isBST bool
	minVal int
	maxVal int
	sum int
}

func maxSumBST(root *TreeNode) int {
	bestSum := 0

	var dfs func(node *TreeNode) Result

	dfs = func(node *TreeNode) Result {
		if node == nil {
			return Result{
				isBST: true,
				minVal: math.MaxInt32,
				maxVal: math.MinInt32,
				sum: 0,
			}
		}

		left := dfs(node.Left)
		right := dfs(node.Right)

		if left.isBST &&
			right.isBST &&
			left.maxVal < node.Val &&
			node.Val < right.minVal {

			currentSum := left.sum + right.sum + node.Val

			if currentSum > bestSum {
				bestSum = currentSum
			}

			minValue := min(left.minVal, node.Val)
			maxValue := max(right.maxVal, node.Val)

			return Result{
				isBST: true,
				minVal: minValue,
				maxVal: maxValue,
				sum: currentSum,
			}
		}

		return Result{
			isBST: false,
		}
	}

	dfs(root)

	return bestSum
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

The Go implementation mirrors the Python approach closely.

Since Go does not support tuple returns as conveniently as Python, a Result struct is used to package the subtree information.

Instead of math.inf, the implementation uses:

• math.MaxInt32
• math.MinInt32

These serve as sentinel boundary values for empty subtrees.

Go also requires explicit helper functions for min() and max() operations.

Worked Examples

Example 1

Input:

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

Tree structure:

        1
      /   \
     4     3
    / \   / \
   2   4 2   5
              / \
             4   6

We process nodes bottom up.

Node	Left BST	Right BST	Valid BST?	Subtree Sum	Max Answer
2	Yes	Yes	Yes	2	2
4	Yes	Yes	Yes	4	4
4(root-left)	Yes	Yes	No	invalid	4
2(right-left)	Yes	Yes	Yes	2	4
4	Yes	Yes	Yes	4	4
6	Yes	Yes	Yes	6	6
5	Yes	Yes	Yes	15	15
3	Yes	Yes	Yes	20	20
1	No	Yes	No	invalid	20

Final answer:

20

The subtree rooted at 3 is the largest valid BST.

Example 2

Input:

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

Tree:

      4
     /
    3
   / \
  1   2

Processing:

Node	Valid BST?	Sum
1	Yes	1
2	Yes	2
3	No	invalid
4	No	invalid

The best valid BST is the single node 2.

Final answer:

2

Example 3

Input:

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

Tree:

    -4
   /  \
 -2   -5

Every valid BST subtree has a negative sum.

Node	BST Sum	Global Best
-2	-2	0
-5	-5	0
-4	invalid	0

Since the empty BST is allowed, the answer remains:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node is processed exactly once
Space	O(h)	Recursive call stack depth equals tree height

The DFS traversal visits each node a single time and performs constant work per node. Therefore, the total time complexity is linear.

The space complexity comes from recursion depth. In the worst case of a completely skewed tree, the height becomes n, leading to O(n) stack usage. In a balanced tree, the recursion depth is O(log n).

Test Cases

# Definition for testing
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Solution implementation
from typing import Optional
import math

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.best_sum = 0

        def dfs(node):
            if not node:
                return True, math.inf, -math.inf, 0

            left_ok, left_min, left_max, left_sum = dfs(node.left)
            right_ok, right_min, right_max, right_sum = dfs(node.right)

            if left_ok and right_ok and left_max < node.val < right_min:
                total = left_sum + right_sum + node.val

                self.best_sum = max(self.best_sum, total)

                return (
                    True,
                    min(left_min, node.val),
                    max(right_max, node.val),
                    total
                )

            return False, 0, 0, 0

        dfs(root)

        return self.best_sum

sol = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(4, TreeNode(2), TreeNode(4)),
    TreeNode(3, TreeNode(2), TreeNode(5, TreeNode(4), TreeNode(6)))
)
assert sol.maxSumBST(root1) == 20  # complex mixed tree

# Example 2
sol = Solution()
root2 = TreeNode(4, TreeNode(3, TreeNode(1), TreeNode(2)))
assert sol.maxSumBST(root2) == 2  # only single node BST

# Example 3
sol = Solution()
root3 = TreeNode(-4, TreeNode(-2), TreeNode(-5))
assert sol.maxSumBST(root3) == 0  # all negative values

# Single node positive
sol = Solution()
root4 = TreeNode(10)
assert sol.maxSumBST(root4) == 10  # simplest valid BST

# Single node negative
sol = Solution()
root5 = TreeNode(-10)
assert sol.maxSumBST(root5) == 0  # empty BST better

# Entire tree is valid BST
sol = Solution()
root6 = TreeNode(
    5,
    TreeNode(3, TreeNode(2), TreeNode(4)),
    TreeNode(8, TreeNode(6), TreeNode(10))
)
assert sol.maxSumBST(root6) == 38  # whole tree valid

# Duplicate values invalidate BST
sol = Solution()
root7 = TreeNode(2, TreeNode(2), TreeNode(3))
assert sol.maxSumBST(root7) == 3  # duplicates not allowed

# Skewed increasing tree
sol = Solution()
root8 = TreeNode(1, None, TreeNode(2, None, TreeNode(3)))
assert sol.maxSumBST(root8) == 6  # valid skewed BST

# Deep invalid subtree
sol = Solution()
root9 = TreeNode(
    10,
    TreeNode(5),
    TreeNode(15, TreeNode(6), TreeNode(20))
)
assert sol.maxSumBST(root9) == 41  # subtree rooted at 15 valid

# Empty child handling
sol = Solution()
root10 = TreeNode(1, TreeNode(0), None)
assert sol.maxSumBST(root10) == 1  # valid small BST

Test	Why
Mixed valid and invalid tree	Verifies selective subtree evaluation
Only single-node BSTs	Ensures invalid parents are rejected
All negative values	Confirms empty BST result of 0
Single positive node	Smallest non-empty valid BST
Single negative node	Confirms max remains 0
Entire tree valid	Verifies full-tree accumulation
Duplicate values	Tests strict BST inequality
Right-skewed BST	Tests recursive depth handling
Deep descendant violation	Ensures full BST constraints checked
Missing child subtree	Validates null subtree handling

Edge Cases

All Values Are Negative

A common mistake is forcing the algorithm to return the largest negative BST sum. However, the problem explicitly allows choosing the empty BST with sum 0.

For example:

[-4, -2, -5]

Every subtree has a negative sum, so the correct answer is 0.

The implementation handles this naturally because the global answer starts at 0 and is updated only when a larger sum is found.

Duplicate Values

BST rules require strict inequality.

This means:

left_max < node.val < right_min

Using <= or >= would incorrectly accept duplicate values.

For example:

    2
   /
  2

This is not a valid BST.

The implementation explicitly uses strict comparison operators, ensuring duplicates invalidate the subtree.

Invalid Deep Descendants

A subtree may appear valid when checking only direct children but fail because of deeper descendants.

Example:

      10
     /  \
    5   15
       /
      6

Although 6 < 15, the entire right subtree violates BST rules because all nodes in the right subtree must be greater than 10.

The algorithm correctly detects this by propagating subtree minimum and maximum values upward during DFS.

Highly Skewed Trees

A tree may degenerate into a linked list shape:

1
 \
  2
   \
    3

This creates recursion depth proportional to the number of nodes.

The algorithm still works correctly because each node is processed once, though recursion depth becomes O(n) in the worst case.