Add the Sum of All Larger Keys to Every Node

Implement addGreaterSums

You 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.

Example 1:

Input: root = [30,10,50,5,20,40,60,null,null,15,25]

Output: [180,250,110,255,225,150,60,null,null,240,205]

Example 2:

Input: root = [6,3]

Output: [6,9]

Example 3:

Input: root = []

Output: []

+ 11 hidden test cases run on Submit.

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

root =

[30, 10, 50, 5, 20, 40, 60, null, null, 15, 25]