The best search subtree
Find the subtree that is a valid binary search tree and has the largest sum, by returning from each subtree whether it is a search tree, its sum, and its smallest and largest values. About 24 minutes.
What the parent needs
A node is the root of a search tree when its left side is a search tree whose largest value is below the node, and its right side is a search tree whose smallest value is above it.
So each subtree must report four things: whether it is a search tree, its sum, its smallest value and its largest value.
info = (True, 12, 3, 9) # is_bst, sum, min, max
- best
- 8
Each leaf is a search tree by itself: sums 1, 8, 5 and 7. The best so far is 8.
Empty subtrees and failures
An empty subtree is a search tree with sum zero. Give it a minimum of infinity and a maximum of minus infinity, so that the checks against the node pass without special cases.
If a node fails the test, it reports that it is not a search tree, and so do all its ancestors, but the best sum found lower down is kept. The answer is the largest sum found over all valid subtrees, and at least zero for the empty tree.
ok = left_max < node.val < right_min
A node has value 5, and its left side has a largest value of 7. Is the node the root of a search tree?
- ANo, since a value on the left is not smaller than the node
- BYes, if both sides are search trees
- CIt depends on the right side
Show the answer
No, since a value on the left is not smaller than the node. In a search tree everything on the left is below the node.
Maximum sum binary search tree
Given the root of a binary tree, return the maximum sum of the node values of any subtree that is also a binary search tree (all values in the left subtree are smaller than the node, all in the right are larger, and both subtrees are search trees). If every such subtree has a negative sum, return 0, which stands for the empty subtree.
root = [1, 4, 3, 2, 4, 2, 5, null, null, null, null, null, null, 4, 6] → 20
1 ≤ number of nodes ≤ 5,000 · -4,000 ≤ node.val ≤ 4,000