Frontend School

Transform BST to Greater Sum Tree

DSA
medium

Transform BST to Greater Sum Tree

Medium
Tree
Binary Search Tree
DFS
In-order Traversal

Overview

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.

What you need to do / Task

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 & output

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:

  • The 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.

Clarifications

  • An empty tree (where root is null) should be handled gracefully. In this case, return null.

Examples

1

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

2

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

3

Example 3

Input:

root = [1]

Output:

[1]

Note:

Original Tree (in-order): 1 Transformed values: 1 -> 1

Constraints

Constraints & assumptions

  • The number of nodes in the BST will be between 0 and 10^4.
  • Node values (Node.val) will be between 0 and 10^5.
  • All original node values in the BST are unique.
  • The input tree is guaranteed to be a valid Binary Search Tree.

What interviewers evaluate

  • Correctness: The solution accurately transforms the BST into a Greater Sum Tree according to the problem definition.
  • Efficiency: The solution demonstrates optimal time and space complexity for the given constraints.
  • Code Quality: The code is clean, readable, well-structured, and handles edge cases gracefully.
  • Algorithmic Understanding: Demonstrates a clear grasp of BST properties and appropriate traversal techniques.

Loading editor...