text: Convert an arbitrary Binary Tree to a tree that holds Children Sum Property | Program to convert an aribitary binary tree to a tree that holds children sum property ; A binary tree node ; This function is used to increment left subtree ; 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 ; Helper function that allocates a new node with the given data and NULL left and right pointers . ; Driver program to test above functions
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE struct node { int data ; struct node * left ; struct node * right ; } ; void increment ( struct node * node , int diff ) ; void convertTree ( struct 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 ( struct 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 ( struct node * node ) { if ( node == NULL ) return ; printInorder ( node -> left ) ; printf ( " % d ▁ " , node -> data ) ; printInorder ( node -> right ) ; } struct node * newNode ( int data ) { struct node * node = ( struct node * ) malloc ( sizeof ( struct node ) ) ; node -> data = data ; node -> left = NULL ; node -> right = NULL ; return ( node ) ; } int main ( ) { struct node * root = newNode ( 50 ) ; root -> left = newNode ( 7 ) ; root -> right = newNode ( 2 ) ; root -> left -> left = newNode ( 3 ) ; root -> left -> right = newNode ( 5 ) ; root -> right -> left = newNode ( 1 ) ; root -> right -> right = newNode ( 30 ) ; printf ( " Inorder traversal before conversion " printInorder ( root ) ; convertTree ( root ) ; printf ( " Inorder traversal after conversion " printInorder ( root ) ; getchar ( ) ; return 0 ; }