Update every key in BST to contain sum of all greater keys

Given a binary search tree, modify it such that every key is updated to contain sum of all greater keys present in BST.

 

For example, BST shown on the left should be updated to BST on the right.

 
Update Key BST

 

1. Using in-order traversal –

 

We can solve this problem by in-order traversal by calculating the sum of all nodes present in a binary tree in advance. Then for each node, sum of all greater keys for any node can be updated in constant time using total sum and sum of nodes visited so far.

 
C++ implementation –
 

Download   Run Code

Output:

38 36 33 29 24 18 10

 

2. Using Reverse in-order traversal –

 

Above solution traverses the tree two times. We can solve this problem in single traversal by traversing the tree in reverse Inorder. Now, keys will be visited in descending order and sum of all greater keys for any node can be updated in constant time by keeping track of sum of nodes visited so far.

 
C++ implementation –
 

Download   Run Code

Output:

38 36 33 29 24 18 10

 
The time complexity of above solution is O(n).
 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Amit
Guest

Really awesome solution. I enjoy your posts a lot. Thank you

David
Guest

Nice One!