Add all greater values to every node in a BST

Given a Binary Search Tree (BST), modify it so that all greater values in the given BST are added to every node.

Solution :

• Reverse of InOrder traversal with sum
• Second Option
  • Traverse tree in InOrder and extract all node data to array in O(n)
  • Sum all data of array in reverse order in O(n)
  • Again Traverse tree in InOrder and replace node value with array in O(n)

Algorithm :

• Take sum class object to hold the sum of nodes (because java doesn’t support call by reference, so we need object)
• Traverse reverse InOrder (means Right – Root – Left)
  • If node is null then
    • return
  • Recursively call for right child
  • Set sum = sum + node.data
  • Set node = sum
  • Recursively call for left child

Latest Source Code:
Github: SumOfAllGreaterValueInBST.java

Output:

   50       
  / \   
 /   \  
 30   70   
/ \ / \ 
20 40 60 80 
                
After Sum : 
   260       
  / \   
 /   \  
 330   150   
/ \ / \ 
350 300 210 80