Add Every Larger Key
MediumTrees
Problem
A loyalty program stores point thresholds (distinct integers) in a binary search tree. Rewrite every node so its new value is its old value plus the sum of all old values greater than it in the tree.
Keep the shape unchanged and return the root.
Example 1
- Input:
- root = [4, 1, 6, 0, 2, 5, 7, null, null, null, 3, null, null, null, 8]
- Output:
- [30, 36, 21, 36, 35, 26, 15, null, null, null, 33, null, null, null, 8]
8 stays 8, 7 becomes 15, 6 becomes 21, ..., 0 becomes 36.
Example 2
- Input:
- root = [0, null, 1]
- Output:
- [1, null, 1]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -10^4 ≤ node.val ≤ 10^4
- All values are distinct.
Hint
Show the first hint
In which order would you like to visit the nodes so that, when you reach one, you already know the sum of everything larger?
Walkthrough
How to approach it
01Clarify before coding
- Is it 'greater than or equal'? Values are distinct, so new value = old value + all strictly greater values.
- Must the shape stay the same? Yes, only values change.
- Can values be negative? Yes; the running sum handles that naturally.
02Brute force
For every node, scan the whole tree and sum the larger values.
Cost: O(n²) time: 10^8 operations for 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.