title: Replace BST nodes with the sum of nodes greater than or equal to the node
body: <p>I would like to know the algorithm for the following problem:<br>
  "Given a BST(There can be duplicate nodes), replace every node with value which is sum of values of all nodes greater than equal to the current node."</p>
  
  <p>Example:</p>
  
  <blockquote>
    <blockquote>
  <pre><code>                              5                15
                              2  10     o/p:   17  10
  </code></pre>
    </blockquote>
  </blockquote>
  
  <p>I did it with reverse in-order traversal keeping a variable 'sum'. Here is the code:</p>
  
  <pre><code>public static void replaceNodeValue(BSTNode root, int[] sum) {  
  if (root == null) return;       
  replaceNodeValue(root.right, sum);      
  root.data = (sum[0] = sum[0] + root.data);      
  replaceNodeValue(root.left, sum);
  }
  </code></pre>
  
  <p>The problem is this code works only if the tree doesn't contain a duplicate node. I am looking for the correct algorithm which will handle duplicate nodes also. </p>
  
  <p>One case for which the code will fail is:</p>
  
  <blockquote>
    <blockquote>
  <pre><code>                               5
                              5     5
  </code></pre>
    </blockquote>
  </blockquote>
  
  <p>Please help.
  Thanks</p>