405. Convert BST to Greater Tree
You receive the root of a binary search tree whose keys are all distinct. Transform it, in place, into a greater tree: every node's key must become its original key plus the sum of every key in the tree that is greater than it. The largest key therefore keeps its value, and the smallest ends up holding the sum of the entire tree.
The shape of the tree does not change — only the stored values do. Return the root of the transformed tree.
The judge reads the BST in level order (with null for missing children) and prints your transformed tree the same way: values separated by single spaces, null for a missing child of a printed node, trailing null tokens removed.
Example 1:
Input: convert_bst(root of [5, 2, 13])
Output: the tree [18, 20, 13]
Explanation: 13 is the largest key so it stays 13. For 5, the greater keys sum to 13, so 5 becomes 5 + 13 = 18. For 2, they sum to 5 + 13 = 18, so 2 becomes 20.
Example 2:
Input: convert_bst(root of [3, 1, 4, null, 2])
Output: the tree [7, 10, 4, null, 9]
Explanation: 4 stays 4; 3 becomes 3 + 4 = 7; 2 becomes 2 + 3 + 4 = 9; 1 becomes 1 + 2 + 3 + 4 = 10. The shape — including 2 hanging as 1's right child — is untouched.
Constraints:
- 1 ≤ number of nodes ≤ 10⁴
- -10⁴ ≤ node key ≤ 10⁴
- All keys are distinct
- The input is a valid binary search tree
Hints:
Which traversal of a BST visits the keys in ascending order? Now mirror it — right subtree, node, left subtree — and you visit the keys in descending order instead.
Walk the tree in that descending order carrying a single running sum. When you arrive at a node, the running sum already equals the total of every key greater than it: add the node's own key to the sum, store the sum as the new value, and continue into the left subtree.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [5, 2, 13]
Expected output: [18, 20, 13]