Monthly Archives: November 2016

Add all greater values to every node in a BST

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