Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).
Assume a BST is defined as follows:
Example 1:
Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6] Output: 20 Explanation: 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 Explanation: 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 Explanation: All values are negatives. Return an empty BST.
Constraints:
[1, 4 * 104].-4 * 104 <= Node.val <= 4 * 104Problem Overview: You are given a binary tree that is not necessarily a binary search tree. The goal is to find the maximum sum of values among all subtrees that satisfy the binary search tree property. Any node can be the root of such a subtree, and the subtree must obey BST ordering rules: left values smaller than the node and right values greater.
Approach 1: Brute Force Subtree Validation (O(n^2) time, O(h) space)
Check every node as a potential root of a BST subtree. For each node, perform a validation pass to verify whether the subtree satisfies BST constraints using min/max bounds, then compute the sum of its nodes. This requires traversing the same nodes multiple times. In the worst case (skewed trees), every node triggers a full subtree scan, giving O(n^2) time complexity. Space complexity is O(h) due to recursion depth where h is the tree height.
This approach is straightforward but inefficient. It helps you reason about the problem: each subtree must be validated independently and its sum calculated. The repeated traversal becomes the bottleneck.
Approach 2: Recursive Post-order Traversal (O(n) time, O(h) space)
The optimal solution processes the tree using depth-first search in post-order. Each recursive call returns four pieces of information about the current subtree: whether it is a valid BST, the minimum value inside it, the maximum value inside it, and the sum of all nodes.
Post-order traversal ensures left and right subtrees are evaluated before the parent node. When visiting a node, you combine results from its children. The subtree is a valid BST if:
left.isBST && right.isBST && left.max < node.val < right.min
If the condition holds, compute the new sum as left.sum + right.sum + node.val, update the global maximum, and propagate updated min/max boundaries upward. If the condition fails, mark the subtree as invalid so parent nodes cannot treat it as a BST.
This technique resembles bottom-up dynamic programming on a binary tree. Each node contributes a small state summary that allows its parent to determine BST validity without re-traversing nodes. Every node is processed exactly once, producing O(n) time complexity with O(h) recursion stack space.
Recommended for interviews: Interviewers expect the post-order DFS solution. The brute force approach shows you understand BST validation but does not scale. The recursive post-order method demonstrates tree DP thinking: aggregate subtree properties, propagate constraints upward, and compute the answer in a single traversal.
In this approach, we perform a post-order traversal of the tree. For each node, we compute whether its left and right subtrees form BSTs, and if they do, their sum. The maximum BST sum is updated whenever a valid BST subtree is found.
We use a helper function that returns four values: whether the subtree is a BST, the sum of all nodes in this subtree, the minimum value in this subtree, and the maximum value in this subtree.
The code defines a helper function postOrder that concurrently checks for a BST and calculates its sum. This function is called recursively for left and right subtrees, updating the maximum sum as it finds BSTs.
Time Complexity: O(n), as each node is visited exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack.
To determine whether a tree is a binary search tree, it needs to meet the following four conditions:
Therefore, we design a function dfs(root), the return value of the function is a quadruple (bst, mi, mx, s), where:
bst indicates whether the tree with root as the root is a binary search tree. If it is a binary search tree, then bst = 1; otherwise bst = 0;mi represents the minimum value of the tree with root as the root;mx represents the maximum value of the tree with root as the root;s represents the sum of all nodes of the tree with root as the root.The execution logic of the function dfs(root) is as follows:
If root is an empty node, return (1, +infty, -infty, 0), indicating that the empty tree is a binary search tree, the minimum value and maximum value are positive infinity and negative infinity respectively, and the sum of nodes is 0.
Otherwise, recursively calculate the left subtree and right subtree of root, and get (lbst, lmi, lmx, ls) and (rbst, rmi, rmx, rs) respectively, then judge whether the root node meets the conditions of the binary search tree.
If lbst = 1 and rbst = 1 and lmx < root.val < rmi, then the tree with root as the root is a binary search tree, and the sum of nodes s= ls + rs + root.val. We update the answer ans = max(ans, s), and return (1, min(lmi, root.val), max(rmx, root.val), s).
Otherwise, the tree with root as the root is not a binary search tree, we return (0, 0, 0, 0).
We call dfs(root) in the main function. After execution, the answer is ans.
The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Recursive Post-order Traversal | Time Complexity: |
| DFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subtree Validation | O(n^2) | O(h) | Conceptual starting point when learning BST validation or reasoning about subtree checks |
| Recursive Post-order Traversal (Tree DP) | O(n) | O(h) | Optimal approach for interviews and production; processes each node once |
Largest Binary Search Tree | Maximum Sum BST in Binary Tree | Leetcode • Coder Army • 17,833 views views
Watch 9 more video solutions →Practice Maximum Sum BST in Binary Tree with our built-in code editor and test cases.
Practice on FleetCode