Transform BST to Greater Sum Tree
In travel technology, data aggregation and transformation are critical for insights and optimizations. Consider a scenario where trip data, such as costs or user ratings, is stored in a Binary Search Tree (BST) for efficient lookup. We need to transform this tree such that each trip's value reflects a cumulative metric: the sum of its own original value and the original values of all trips that are "greater than" or "more significant than" it. This transformation enables rapid querying of aggregated values, crucial for real-time decision-making.
You are given the root of a Binary Search Tree (BST). Your task is to convert it into a "Greater Sum Tree". In a Greater Sum Tree, every node's value is replaced with the sum of all node values in the original BST that are greater than or equal to the node's original value.
You should modify the tree in-place and return the root of the transformed tree.
Input:
root: The root node of a Binary Search Tree (BST). Each TreeNode has an integer val, a left child, and a right child.Output:
root of the modified BST, which is now a Greater Sum Tree. The structure of the tree should remain the same; only the val of each node should be updated.root is null) should be handled gracefully. In this case, return null.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 Transformed values: 8 -> 8 7 -> 7+8 = 15 6 -> 6+7+8 = 21 5 -> 5+6+7+8 = 26 4 -> 4+5+6+7+8 = 30 3 -> 3+4+5+6+7+8 = 33 2 -> 2+3+4+5+6+7+8 = 35 1 -> 1+2+3+4+5+6+7+8 = 36 0 -> 0+1+2+3+4+5+6+7+8 = 36
Example 2
Input:
root = [0,null,1]
Output:
[1,null,1]
Note:
Original Tree (in-order): 0, 1 Transformed values: 1 -> 1 0 -> 0+1 = 1
Example 3
Input:
root = [1]
Output:
[1]
Note:
Original Tree (in-order): 1 Transformed values: 1 -> 1
Constraints
0 and 10^4.Node.val) will be between 0 and 10^5.Loading editor...