Add Every Bigger Key

Medium

You are given the root of a binary search tree: for every node, all keys in its left subtree are smaller than its key and all keys in its right subtree are larger. All keys are distinct. Replace each node's key with the sum of its original key and every original key in the tree that is larger. The shape of the tree stays the same. Return the root of the updated tree (None for an empty tree).

Example 1

root=tree_node([6, 2, 9, None, 4]) → [15, 21, 9, None, 19]

9 is the largest key and stays 9. 6 gets 9 added and becomes 15, 4 gets 6 and 9 (19), and 2 gets all the others (21).

Example 2

root=tree_node([-3, None, 5]) → [2, None, 5]

5 stays the same and -3 becomes -3 + 5 = 2.

Example 3

root=tree_node([]) → None

Constraints

0 ≤ number of nodes ≤ 10⁴
-10⁴ ≤ Node.val ≤ 10⁴
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 Keep Only a Range of a Search Tree Medium

Input

root=tree_node([6, 2, 9, None, 4])

Expected

[15, 21, 9, None, 19]

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