Add everything that is bigger
Replace each value in a search tree by itself plus the sum of all values greater than it, by walking the tree from the largest value down while keeping a running total. About 14 minutes.
Largest first
Each node should end up holding its own value plus the sum of every value bigger than it. If you visit the nodes from the largest to the smallest, then when you arrive at a node, all the bigger values have already been seen.
The inorder walk goes smallest to largest. Swap the two recursive calls: right subtree first, then the node, then the left subtree.
walk(node.right) ... walk(node.left)
- total
- 7
The largest is 7. Total 7, so 7 stays 7.
Update in the middle
When the walk reaches a node, add the node's old value to the running total. The total now holds the node's value plus all larger values, which is exactly the new value. Store it in the node.
Do these two steps in this order, because the total must include the node's old value. After the whole walk, return the root: its shape did not change.
total[0] += node.val node.val = total[0]
Why must the right subtree be visited before the node?
- AIts values are all bigger, and must be added to the total first
- BIts values are smaller
- CIt is simply the usual order
Show the answer
Its values are all bigger, and must be added to the total first. In a search tree the right side holds the larger values.
Convert a search tree to a greater tree
Given the root of a binary search tree with different values, change every node's value so that it equals its original value plus the sum of all original values greater than it in the tree. Return the root.
root = [4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8] → [30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]
0 ≤ number of nodes ≤ 10,000 · 0 ≤ node.val ≤ 10,000 · it is a valid search tree