Running Totals in a Search Tree

Medium

You are given the root of a binary search tree: at every node, all keys in the left subtree are smaller than the node's key and all keys in the right subtree are larger. All keys are distinct. Replace each node's key with the sum of that key and every key in the tree that is larger than it. Keep the shape of the tree and return its root.

Example 1

root=tree_node([6, 3, 9]) → [15, 18, 9]

No key is larger than 9, so it stays 9. 6 gains 9 and becomes 15. 3 gains 6 and 9 and becomes 18.

Example 2

root=tree_node([5, None, 8, 7]) → [20, None, 8, 15]

8 stays 8, 7 becomes 7 + 8 = 15, and 5 becomes 5 + 7 + 8 = 20. The shape of the tree does not change.

Example 3

root=tree_node([0]) → [0]

Constraints

1 ≤ number of nodes ≤ 100
0 ≤ Node.val ≤ 100
All keys are distinct and the tree is a valid search tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Binary Tree

Similar problems

Is It a Search Tree? Medium Two Mixed-Up Nodes Medium K-th Smallest in a Search Tree Medium Biggest Search Subtree Medium Add Every Bigger Key Medium

Input

root=tree_node([6, 3, 9])

Expected

[15, 18, 9]

Run checks the first 3 tests in your browser. Submit checks all 48 tests on the server, hidden ones included.