Frontend School

Convert BST to Greater Tree

DSA
medium

Convert BST to Greater Tree

Medium
Tree
Binary Search Tree
Recursion
In-order Traversal

Overview

In many data-driven applications, especially within financial analytics or reporting systems, the ability to quickly aggregate or summarize data based on relative values is crucial. Imagine a Binary Search Tree (BST) where each node represents a transaction value. We might need to transform this tree to efficiently answer queries like "what is the sum of all transactions greater than or equal to a specific value?". This problem challenges you to convert a standard BST into a "Greater Tree" where each node's value is updated to reflect such an aggregation.

What you need to do / Task

Implement a function bstToGreaterTree that takes the root of a Binary Search Tree. Your task is to modify the tree in-place such that each node's new value is the sum of its original value and the values of all other nodes in the original tree that are greater than or equal to the current node's original value. After the transformation, return the root of the modified tree.

Input & output

Input: root: A TreeNode representing the root of a Binary Search Tree. Each TreeNode has three properties:

  • val: a number representing the node's value.
  • left: a TreeNode or null, pointing to the left child.
  • right: a TreeNode or null, pointing to the right child.

Output: Return the TreeNode representing the root of the modified "Greater Tree". The structure of the tree should remain the same; only the val of each node should be updated.

Clarifications

  • If the input root is null (an empty tree), the function should return null.
  • The modification must be performed in-place, meaning you should update the val property of existing TreeNode objects rather than creating new nodes.
  • All Node.val in the original tree are guaranteed to be unique.
  • The given tree will always be a valid Binary Search Tree.

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. New values are calculated as follows:

  • Node 8: 8
  • Node 7: 7 + 8 = 15
  • Node 6: 6 + 7 + 8 = 21
  • Node 5: 5 + 6 + 7 + 8 = 26
  • Node 4: 4 + 5 + 6 + 7 + 8 = 30
  • Node 3: 3 + 4 + 5 + 6 + 7 + 8 = 33
  • Node 2: 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35
  • Node 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = 36
  • Node 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.

  • Node 1: 1
  • Node 0: 0 + 1 = 1
3

Example 3

Input:

root = [1]

Output:

[1]

Note:

For a single node, there are no greater nodes, so its value remains unchanged.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is in the range [0, 10^4].
  • -10^4 <= Node.val <= 10^4.
  • All Node.val are unique.
  • The given tree is always a valid Binary Search Tree.

Out of scope

  • Input validation (e.g., checking if the input tree is indeed a valid BST, handling non-numeric values).
  • Specific error handling beyond returning null for an empty tree.

What interviewers evaluate

  • Correctness of the BST transformation logic for all nodes.
  • Efficiency of the algorithm, particularly its time and space complexity characteristics.
  • Effective utilization of BST properties to devise an optimal solution.
  • Ability to handle edge cases such as an empty tree or a single-node tree.
  • Overall code quality, including readability, structure, and adherence to best practices.

Loading editor...