Practice/Microsoft/Leetcode 538. Convert BST to Greater Tree

Leetcode 538. Convert BST to Greater Tree

CodingMust

Problem

You are given the root of a binary search tree where each node contains a unique integer value. Transform this tree into an accumulated tree where every node's new value equals its original value plus the sum of all node values that are strictly greater than it.

The transformation should be performed in-place, modifying the existing tree structure rather than creating a new one.

Requirements

1. Modify each node's value to include the sum of all greater values in the tree
2. Perform the transformation in-place without creating a new tree
3. Return the root of the modified tree
4. Handle edge cases including empty trees and single-node trees

Constraints

• The number of nodes in the tree is in the range [0, 10^4]
• -10^4 ≤= Node.val ≤= 10^4
• All values in the BST are unique
• The given tree is guaranteed to be a valid binary search tree

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,33,26,15,null,null,null,30,null,null,null,8] Explanation: Node with value 0: 0 + (1+2+3+4+5+6+7+8) = 36 Node with value 1: 1 + (2+3+4+5+6+7+8) = 36 Node with value 2: 2 + (3+4+5+6+7+8) = 33 Node with value 3: 3 + (4+5+6+7+8) = 30 And so on...

Example 2:

Input: root = [1,null,2,null,3,null,4] Output: [10,9,7,4] Explanation: Node 1: 1 + (2+3+4) = 10 Node 2: 2 + (3+4) = 9 Node 3: 3 + 4 = 7 Node 4: 4

Example 3:

Input: root = [5] Output: [5] Explanation: Single node has no greater values, remains unchanged