Convert an arbitrary Binary Tree to a tree that holds Children Sum Property | C ++ Program to convert an aribitary binary tree to a tree that hold children sum property ; Constructor that allocates a new node with the given data and NULL left and right pointers . ; 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 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; class node { public : int data ; node * left ; node * right ; node ( int data ) { this -> data = data ; this -> left = NULL ; this -> right = NULL ; } } ; void increment ( node * node , int diff ) ; 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 ) ; cout << node -> data << " ▁ " ; printInorder ( node -> right ) ; } int main ( ) { node * root = new node ( 50 ) ; root -> left = new node ( 7 ) ; root -> right = new node ( 2 ) ; root -> left -> left = new node ( 3 ) ; root -> left -> right = new node ( 5 ) ; root -> right -> left = new node ( 1 ) ; root -> right -> right = new node ( 30 ) ; cout << " Inorder traversal before conversion : " printInorder ( root ) ; convertTree ( root ) ; cout << " Inorder traversal after conversion : " printInorder ( root ) ; return 0 ; }