Add the Sum of All Larger Keys to Every Node
Solve this ProblemYou are given the root of a binary search tree with distinct values. Change every node's value to its original value plus the sum of all original values in the tree that are strictly greater than it. Keep the shape of the tree and return its root.
Recomputing each sum with a scan is slow. Visiting the nodes from the largest to the smallest with a running total gives each node its new value exactly as it is reached.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
Replace every node's value by (its ORIGINAL value) + (the sum of all ORIGINAL values in the tree that are strictly greater than it). Change the values in place, keep the shape, and return the root (checked as a level-order list) - ◆
The largest value therefore stays unchanged, and the smallest value becomes the sum of all values in the tree
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — For Every Node, Add Up All the Larger Values
BruteFirst save the ORIGINAL values in a list (an inorder walk), because the tree itself is about to be modified. Then visit every node and add up, by scanning the whole list, all original values that are strictly greater than the node's own; add that sum to the node. Every node scans n values, so it takes O(n²) time, plus O(n) for the list.
O(n²)O(n)1class Solution {
2 public TreeNode addGreaterSums(TreeNode root) {
3 List<Integer> vals = new ArrayList<>();
4 inorder(root, vals);
5 relabel(root, vals);
6 return root;
7 }
8
9 private void inorder(TreeNode node, List<Integer> vals) {
10 if (node == null) return;
11 inorder(node.left, vals);
12 vals.add(node.val);
13 inorder(node.right, vals);
14 }
15
16 private void relabel(TreeNode node, List<Integer> vals) {
17 if (node == null) return;
18 int extra = 0;
19 for (int v : vals) {
20 if (v > node.val) extra += v;
21 }
22 node.val += extra;
23 relabel(node.left, vals);
24 relabel(node.right, vals);
25 }
26}Optimal — Reverse Inorder With a Running Total
OptimalVisit the nodes from the LARGEST to the smallest: right subtree first, then the node, then the left subtree (reverse inorder). Keep a running total of the values seen so far. When a node is reached, every value greater than it has already been added to the total, so adding the node's own value gives exactly "original + sum of greater values" — write that total into the node. Each node is handled once: O(n) time and O(h) recursion space, and no list of values is needed.
O(n)O(h)1class Solution {
2 private int total;
3
4 public TreeNode addGreaterSums(TreeNode root) {
5 total = 0;
6 walk(root);
7 return root;
8 }
9
10 private void walk(TreeNode node) {
11 if (node == null) return;
12 walk(node.right);
13 total += node.val;
14 node.val = total;
15 walk(node.left);
16 }
17}