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