Frontend School

Convert BST to Greater Sum Tree

DSA
medium

Convert BST to Greater Sum Tree

Medium
Tree
Binary Search Tree
Traversal
Recursion

Overview

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.

What you need to do / Task

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

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:

  • A TreeNode representing the root of the modified Greater Sum Tree.

Clarifications

  • An empty tree (i.e., root is null) should result in returning null.
  • The input tree is guaranteed to be a valid Binary Search Tree.
  • Node values can be positive, negative, or zero integers.

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 BST (in-order): 0, 1, 2, 3, 4, 5, 6, 7, 8.

  • Node 8: No greater values. New val = 8.
  • Node 7: Greater values = [8]. New val = 7 + 8 = 15.
  • Node 6: Greater values = [7, 8]. New val = 6 + 7 + 8 = 21.
  • Node 5: Greater values = [6, 7, 8]. New val = 5 + 6 + 7 + 8 = 26.
  • Node 4: Greater values = [5, 6, 7, 8]. New val = 4 + 5 + 6 + 7 + 8 = 30.
  • Node 3: Greater values = [4, 5, 6, 7, 8]. New val = 3 + 4 + 5 + 6 + 7 + 8 = 33.
  • Node 2: Greater values = [3, 4, 5, 6, 7, 8]. New val = 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35.
  • Node 1: Greater values = [2, 3, 4, 5, 6, 7, 8]. New val = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36.
  • Node 0: Greater values = [1, 2, 3, 4, 5, 6, 7, 8]. New val = 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36.
2

Example 2

Input:

root = [0,null,1]

Output:

[1,null,1]

Note:

Original BST (in-order): 0, 1.

  • Node 1: No greater values. New val = 1.
  • Node 0: Greater values = [1]. New val = 0 + 1 = 1.
3

Example 3

Input:

root = [1]

Output:

[1]

Note:

Original BST (in-order): 1. No greater values. New val = 1.

4

Example 4

Input:

root = []

Output:

null

Note:

An empty tree remains null.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • -10^9 <= Node.val <= 10^9.

What interviewers evaluate

  • Correctness of the algorithm for transforming the BST.
  • Efficient use of time and space complexity.
  • Ability to identify and correctly implement the appropriate tree traversal strategy (e.g., reverse in-order).
  • Clarity, readability, and modularity of the code.

Loading editor...