root of a binary tree holding integer values.
A subtree is a node together with *all* of its descendants. A subtree is a search tree if, for each of its nodes, every value in the left branch is strictly smaller than the node's value and every value in the right branch is strictly larger.
Find the search subtree with the largest sum of values and return that sum. The empty subtree also counts as a search tree with sum 0, so the answer is never negative.
Try to do it in a single traversal.root=tree_node([6, 9, 12, 7, 11, 10, 15]) → 37
The root 6 and its left branch break the order, but the right branch 12 → (10, 15) is a search tree with sum 12 + 10 + 15 = 37. That beats the branch 9 → (7, 11), which sums to 27.
root=tree_node([2, 1, 3, None, None, -5, 4]) → 4
The whole tree fails: -5 sits to the right of 2 although it is smaller. Among the valid subtrees the best is the single node 4 (the subtree 3 → (-5, 4) gives only 2).
root=tree_node([-3, -8, -1]) → 0
Every value is negative, so the empty subtree with sum 0 is the best choice.
Node.val ≤ 4·10⁴root=tree_node([6, 9, 12, 7, 11, 10, 15])
37
Run checks the first 3 tests in your browser. Submit checks all 99 tests on the server, hidden ones included.