Convert BST to Greater Sum Tree
In Clevertap, user data often comes in hierarchical structures. Imagine a Binary Search Tree (BST) representing user scores, where higher scores are more important. We might need to transform this tree so that each user's score reflects not just their own performance, but also the aggregate impact of all users with strictly higher scores. This problem asks you to convert a given BST into a "Greater Sum Tree" (GST) where each node's value is replaced with the sum of its original value and the values of all nodes strictly greater than it.
Given the root of a Binary Search Tree (BST), convert it to a Greater Sum Tree (GST) such that every node's value is changed to the sum of its original value and the values of all nodes strictly greater than the original node.
Your function should return the root of the modified BST.
Input:
root: A TreeNode representing the root of a Binary Search Tree. Each TreeNode has val (number), left (TreeNode or null), and right (TreeNode or null).Output:
TreeNode representing the root of the modified Greater Sum Tree.root is null) should result in returning 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 BST (in-order): 0, 1, 2, 3, 4, 5, 6, 7, 8.
Example 2
Input:
root = [0,null,1]
Output:
[1,null,1]
Note:
Original BST (in-order): 0, 1.
Example 3
Input:
root = [1]
Output:
[1]
Note:
Original BST (in-order): 1. No greater values. New val = 1.
Example 4
Input:
root = []
Output:
null
Note:
An empty tree remains null.
Constraints
[0, 10^4].-10^9 <= Node.val <= 10^9.Loading editor...