Convert an arbitrary Binary Tree to a tree that holds Children Sum Property | A binary tree node ; This function changes a tree to hold children sum property ; If tree is empty or it 's a leaf node then  return true  ; convert left and right subtrees ; If left child is not present then 0 is used as data of left child ; If right child is not present then 0 is used as data of right child ; get the diff of node 's data and children sum  ; If node ' s ▁ children ▁ sum ▁ is ▁ greater ▁ than ▁ the ▁ node ' s data ; THIS IS TRICKY -- > If node 's data is greater than children  sum, then increment subtree by diff  ; - diff is used to make diff positive ; This function is used to increment subtree by diff ; IF left child is not NULL then increment it ; Recursively call to fix the descendants of node -> left ; Else increment right child ; Recursively call to fix the descendants of node -> right ; Given a binary tree , printInorder ( ) prints out its inorder traversal ; first recur on left child ; then print the data of node ; now recur on right child ; Driver program to test above functions
class Node { int data ; Node left , right ; Node ( int item ) { data = item ; left = right = null ; } } class BinaryTree { Node root ; void convertTree ( Node node ) { int left_data = 0 , right_data = 0 , diff ; if ( node == null || ( node . left == null && node . right == null ) ) return ; else { convertTree ( node . left ) ; convertTree ( node . right ) ; if ( node . left != null ) left_data = node . left . data ; if ( node . right != null ) right_data = node . right . data ; diff = left_data + right_data - node . data ; if ( diff > 0 ) node . data = node . data + diff ; if ( diff < 0 ) increment ( node , - diff ) ; } } void increment ( Node node , int diff ) { if ( node . left != null ) { node . left . data = node . left . data + diff ; increment ( node . left , diff ) ; } else if ( node . right != null ) { node . right . data = node . right . data + diff ; increment ( node . right , diff ) ; } } void printInorder ( Node node ) { if ( node == null ) return ; printInorder ( node . left ) ; System . out . print ( node . data + " ▁ " ) ; printInorder ( node . right ) ; } public static void main ( String args [ ] ) { BinaryTree tree = new BinaryTree ( ) ; tree . root = new Node ( 50 ) ; tree . root . left = new Node ( 7 ) ; tree . root . right = new Node ( 2 ) ; tree . root . left . left = new Node ( 3 ) ; tree . root . left . right = new Node ( 5 ) ; tree . root . right . left = new Node ( 1 ) ; tree . root . right . right = new Node ( 30 ) ; System . out . println ( " Inorder ▁ traversal ▁ before ▁ conversion ▁ is ▁ : " ) ; tree . printInorder ( tree . root ) ; tree . convertTree ( tree . root ) ; System . out . println ( " " ) ; System . out . println ( " Inorder ▁ traversal ▁ after ▁ conversion ▁ is ▁ : " ) ; tree . printInorder ( tree . root ) ; } }