Convert BST to Greater Sum Tree

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

What is 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:

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 only problem with this approach is the Time Complexity will be O(N^2). We can do it in one traversal.

We know that right most node in the binary search tree is the biggest node among all node so we will start from there, (reverse inorder traversal).

  1. Since we are visiting the nodes in the decreasing order so all we need to care about maintaining the sum of the nodes visited.
  2. Keep a global variable which 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 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 better understanding.

Complete Code:

Output:

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: