This post is completed by 3 users

  • 0
 Add to List
Medium

189. Convert BST to Greater Sum Tree

Objective: Given a binary search tree (BST), convert it into a greater sum tree.

What is a greater sum tree: Greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.  see the example below

Convert BST to Greater Sum Tree

Approach:

The naive approach will be for every node, traverse the tree and find out all the nodes which are greater and update the node. This approach is fine but the only problem with this approach is the Time Complexity will be O(N^2). We can do it in one traversal.

We know that the rightmost node in the binary search tree is the biggest node among all nodes so we will start from there, (reverse in-order traversal).

  1. Since we are visiting the nodes in decreasing order so we need to care about maintaining the sum of the nodes visited.
  2. Keep a global variable that maintains the sum of the nodes visited till now.
  3. Before updating the node value, store it in temp, we need it later
  4. Updated the node value as sum ( since each node contains a sum of nodes greater than that node which means we need to exclude the node value itself).
  5. Update the sum as sum = sum + temp (for the next node in iteration).
  6. See the code for a better understanding.

Output:

2  5  7  10  12  15  20
69  64  57  47  35  20  0

Related Problems: