Convert BST to Greater Tree

Given the root of a binary search tree, transform it so that each node contains the sum of all values greater than or equal to that node's original value. Pattern focus: BST Iterator Thinking. A reverse inorder traversal visits nodes from largest to smallest, which lets you accumulate a running suffix sum.

Input Format

root = binary tree root

Output Format

root of the transformed greater tree

Constraints

  • 0 <= number of nodes <= 10^5
  • -10^9 <= node values <= 10^9
  • root must satisfy the format described in inputFormat.

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]

Explanation:

Each node is replaced by the sum of all greater-or-equal values.

Example 2:

Input:

root = [2,0,3,-4,1]

Output:

[5,6,3,2,6]

Explanation:

The reverse inorder accumulation updates every node with a suffix sum.

Loading...
Convert BST to Greater Tree - Binary Search Tree