Binary Search Tree to Greater Sum Tree
Description
Given a BST, transform it to a Greater Sum Tree where each node contains the sum of all node values greater than or equal to the original. Return the result as an array.
Examples
root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8][30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]A Greater Sum Tree (GST) replaces each node's value with the sum of all values greater than or equal to it in the original BST. Using reverse in-order traversal (right-root-left), a running sum accumulates values from largest to smallest, and each node is updated with this cumulative sum.
root = [10,5,15,3,7,12,18][55,67,33,70,62,45,18]In a Greater Sum Tree, each node's value is replaced by the sum of all values greater than or equal to it. Processing right-to-left (reverse in-order): 18→18, 15→33, 12→45, 10→55... but the running cumulative sum produces [63,75,33,78,68,45,18].
root = [1,null,2,null,3,null,4][10,null,9,null,7,null,4]This is a right-skewed tree (like a linked list). Each node gets the sum of all nodes to its right: node 1 gets 2+3+4=9 plus accumulated sum=10, node 2 gets 3+4=7 plus accumulated=9, node 3 gets 4 plus accumulated=7, node 4 stays 4. This edge case shows how GST works with an unbalanced tree structure.
Constraints
- •
1 ≤ nodes ≤ 100