Untitled

//      ================ APPROACH 1 ==================
// Time = O(n)
// Space = O(n) [worst case - skewed tree]
// Entry Function
void changeTree(BinaryTreeNode<int> *root) {
    if (root == NULL) return;

    int lVal = root -> left != NULL ? root -> left -> data : INT_MIN;
    int rVal = root -> right != NULL ? root -> right -> data : INT_MIN;
    int mid = root -> data;

    int maxVal = max(mid, max(lVal, rVal));

    // Assign to each node (parent, leftchild, rightchild) max amongst them.
    // This will avoid the situation where left + right < parent (This was a problem in Approach 2, 
    // due to which we had to increase the leftchild and propogate the increased value downwards.)
    root -> data = maxVal;
    if (root -> left != NULL)
        root -> left -> data = maxVal;
    if (root -> right != NULL)
        root -> right -> data = maxVal;
        

    // make LST follow child sum property.
    changeTree(root -> left);
    // make RST follow child sum property.
    changeTree(root -> right);


    // left and right might or might not have increased. In both ways update root value.
    int childSum = 0;
    if (root -> left != NULL)
        childSum += root -> left -> data;
    if (root -> right != NULL)
        childSum += root -> right -> data;
    if (root -> left != NULL || root -> right != NULL)
        root -> data = childSum;
}




//      ================ APPROACH 2 ==================
//  Time = O(n^2) [worst case - skewed tree with decreasing value]
//  Space = O(n) [worst case - skewed tree]

// 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);
    }
}

// Entry Function
// It makes the tree satisfy child sum in a bottom up manner.
void changeTreeApproach2(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);
}