Richest Valid Search Subtree
HardTrees
Problem
You are given an arbitrary binary tree (not necessarily a search tree). A subtree means a node together with all of its descendants.
Among all subtrees that are valid binary search trees (left descendants strictly smaller, right descendants strictly larger, at every node), return the largest sum of node values. The empty subtree counts with sum 0, so the answer is never negative.
Example 1
- Input:
- root = [1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6]
- Output:
- 20
The subtree rooted at 3 (values 2, 3, 4, 5, 6) is a valid search tree with sum 20.
Example 2
- Input:
- root = [4, 3, null, 1, 2]
- Output:
- 2
3's right child 2 is smaller than 3, so the best valid subtree is the single leaf 2.
Example 3
- Input:
- root = [-4, -2, -5]
- Output:
- 0
Every valid subtree has a negative sum; the empty subtree wins.
Constraints
- 1 ≤ number of nodes ≤ 4·10^4
- -4·10^4 ≤ node.val ≤ 4·10^4
- The tree height is at most 500.
Hint
Show the first hint
Checking every subtree separately repeats a lot of work. What could a child tell its parent so the parent can decide in O(1)?
Walkthrough
How to approach it
01Clarify before coding
- Is 'subtree' a node and all its descendants, not an arbitrary connected piece? Yes.
- Can values be negative? Yes, so the best valid subtree may be the empty one with sum 0.
- Are duplicates allowed inside a valid subtree? No, the comparisons are strict.
02Brute force
For every node, validate its subtree with the bounds check and sum it if valid.
Cost: O(n²) time in the worst case (a chain): 1.6·10^9 operations for 4·10^4 nodes.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.