Maximum Sum BST in Binary Tree
Hard · Trees · Dynamic Programming · Tree · Depth-First Search · Binary Search Tree · Binary Tree
Problem
Given the root of a binary tree, look at every subtree that is itself a binary search tree (BST), and return the largest sum of keys among them.
A BST here means: every key in a node's left subtree is strictly less than the node's key, every key in its right subtree is strictly greater, and both subtrees are BSTs too. The empty subtree counts as a BST with sum 0, so the answer is never negative.
Trees are written in level order, with None for a missing child.
Examples
Input: root = [5,9,6,null,null,4,8] Output: 18
The whole tree is not a BST (9 is on the left of 5), but the subtree under 6, with keys 4, 6 and 8, is. Its sum is 18.
Input: root = [-3,-5,-1] Output: 0
The whole tree is a BST with sum -9, and every smaller one is negative too, so the empty subtree's 0 is best.
Input: root = [4,2,6,1,3,5,7] Output: 28
The whole tree is a BST, so its sum, 28, is the largest.
Constraints
- The number of nodes is in the range [1, 4 · 10^4]
- -4 · 10^4 <= Node.val <= 4 · 10^4
Approaches
- Baseline: test the subtree under every node — time O(n²), space O(n)
Follow-up
The same children-first summary answers "how many nodes are in the largest BST subtree?" (the first use case). Drop the BST rule and keep only the sums, and it finds the most valuable subtree of any shape (the second). Could you do it with O(h) extra space instead of O(n)?
Related problems
Start free on Cariara · Coding problems · System design studio
