Convert BST to Greater Tree
In many data-driven applications, especially within financial analytics or reporting systems, the ability to quickly aggregate or summarize data based on relative values is crucial. Imagine a Binary Search Tree (BST) where each node represents a transaction value. We might need to transform this tree to efficiently answer queries like "what is the sum of all transactions greater than or equal to a specific value?". This problem challenges you to convert a standard BST into a "Greater Tree" where each node's value is updated to reflect such an aggregation.
Implement a function bstToGreaterTree that takes the root of a Binary Search Tree. Your task is to modify the tree in-place such that each node's new value is the sum of its original value and the values of all other nodes in the original tree that are greater than or equal to the current node's original value. After the transformation, return the root of the modified tree.
Input:
root: A TreeNode representing the root of a Binary Search Tree. Each TreeNode has three properties:
val: a number representing the node's value.left: a TreeNode or null, pointing to the left child.right: a TreeNode or null, pointing to the right child.Output:
Return the TreeNode representing the root of the modified "Greater Tree". The structure of the tree should remain the same; only the val of each node should be updated.
root is null (an empty tree), the function should return null.val property of existing TreeNode objects rather than creating new nodes.Node.val in the original tree are guaranteed to be unique.Examples
Example 1
Input:
root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output:
[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Note:
Original tree (in-order): 0, 1, 2, 3, 4, 5, 6, 7, 8. New values are calculated as follows:
Example 2
Input:
root = [0,null,1]
Output:
[1,null,1]
Note:
Original tree (in-order): 0, 1.
Example 3
Input:
root = [1]
Output:
[1]
Note:
For a single node, there are no greater nodes, so its value remains unchanged.
Constraints
[0, 10^4].-10^4 <= Node.val <= 10^4.Node.val are unique.null for an empty tree.Loading editor...