Given a BST, transform it into greater sum tree where each node contains sum of all nodes greater than that node.
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