How To 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 –
 
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 –
 
Output:

38 36 33 29 24 18 10
 
The time complexity of above solution is O(n).

Comments

Popular posts from this blog

How to change this to <%Html.ActionLink%> in my asp.net mvc application ?