Friday, June 27, 2014

Transform a BST to greater sum tree

Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
sumBST


Program:


 static void transformBSTSumTree(Node root){
  
  if(root == null) return;
  
  transformBSTSumTreeUtil(root, 0);
  //System.out.println("Sum of BST: "+r);
 }
 
 
 

 private static int transformBSTSumTreeUtil(Node root, int max_sum) {

  if(root == null) return 0;
  
  int r = transformBSTSumTreeUtil(root.right, max_sum);
  
  max_sum = max_sum + r;
  int tmp = root.data;
  root.data = max_sum;
  max_sum = max_sum + tmp;
  
  int l = transformBSTSumTreeUtil(root.left, max_sum);
  
  return l+r+tmp;
  
 }


No comments:

Post a Comment