Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Convert BST to Greater Sum Tree

Objec­tive: Given a binary search tree (BST), con­vert it into greater sum tree.

What is greater sum tree: Greater sum tree is a tree in which every node con­tains the sum of all the nodes which are greater than the node.  see the exam­ple below

Convert BST to Greater Sum Tree

Con­vert BST to Greater Sum Tree

 

Approach:

Naive approach will be for every node, tra­verse the tree and find out all the nodes which are greater and update the node. This approach is fine but only prob­lem with this approach is the Time Com­plex­ity 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 vis­it­ing the nodes in the decreas­ing order so all we need to care about main­tain­ing the sum of the nodes visited.
  2. Keep a global vari­able which main­tains the sum of the nodes vis­ited till now.
  3. Before updat­ing the node value, store it in temp, we need it later
  4. Updated the node value as sum ( since each node con­tains 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 bet­ter understanding.

Com­plete Code:

Out­put:

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

You may also like...