Untitled

// Entry Function
// It makes the tree satisfy child sum in a bottom up manner.
void changeTree(BinaryTreeNode < int > * root) {
    if (root == NULL || (root -> left == NULL && root -> right == NULL)) return;

    // Make LST satisfy child sum
    if (root -> left != NULL)
        changeTree(root -> left);

    // Make RST satisfy child sum
    if (root -> right != NULL)
        changeTree(root -> right);

    int leftVal = root -> left != NULL ? root -> left -> data : 0;
    int rightVal = root -> right != NULL ? root -> right -> data : 0;

    // increase the value of root.
    if (root -> data < leftVal + rightVal)
        root -> data = leftVal + rightVal;
    else
        // increase the value of left child and propogate the changes downwards in LST 
        // because this act has disturbed it property.
        if (root -> data > leftVal + rightVal)
        propogateChanges(root);
}

// If root's LST and RST satisfy child sum property but the root > sum of child
// then propogate the changes in tree downwards.
void propogateChanges(BinaryTreeNode<int> *root) {
    if (root -> left == NULL && root -> right == NULL)  return;

    // By default we change LST and propogate changes in it.
    if (root -> left != NULL) {
        int rightVal = root -> right != NULL ? root -> right -> data : 0;
        root -> left -> data = root -> data - rightVal;
        propogateChanges(root -> left);
    } else { // If LST doesn’t exist then change RST and propogate changes in it.
        root -> right -> data = root -> data;
        propogateChanges(root -> right);
    }
}