Given a Binary Tree, replace the data of each node by the sum of data of all its descendent nodes.(Leaf nodes will have 0)

The Solution for this problem is simple and recursive one. In this problem you have to traverse to the last parent node which has at least 1 child.

So the conditions possible are:

1. Parent has only one leaf  node a) only Left Leaf Node or b) only Right Leaf Node
2. Parent has both children, Left and Right Leaf Nodes.

Now the only thing left is to traverse recursively to the last parent and check wether it has one child or 2 children and store the value of its child or sum of children into its info and if the children do not have any further children then set their value to 0.

#include <stdio.h>
#include <stdlib.h>

struct BST
{
    struct BST* left;
    int info;
    struct BST* right;
};

struct BST* newNode(int);
void printTree(struct BST*);
void replaceParentWithSumOfChildren(struct BST*);



main()
{
    struct BST* root = (struct BST*)malloc(sizeof(struct BST));
    root->info = 10;
    root->left = newNode(5);
    root->right = newNode(15);
    root->left->left = newNode(2);
    root->left->left->left = newNode(1);
    root->right->left = newNode(11);
    root->right->right = newNode(20);
 
    printf("\n\nPrint: TREE PRE-ORDER\n");
    printTree(root);
 
    printf("\n\nPrint: Parent = Sum of Chilren\n");
    replaceParentWithSumOfChildren(root);
    printTree(root);
}

struct BST* newNode(int info)
{
    struct BST* temp = (struct BST*) malloc(sizeof(struct BST*));
    temp->left = NULL;
    temp->right = NULL;
    temp->info = info;
 
    return temp;
}

void printTree(struct BST* root)
{
    struct BST* temp = root;
 
    if(temp != NULL)
    {
        printf(" %d ", temp->info);
        printTree(temp->left);
        printTree(temp->right);
    }
    else
        return;
}

void replaceParentWithSumOfChildren(struct BST* root)
{
    struct BST* temp = root;
 
    if(temp != NULL)
    {
        replaceParentWithSumOfChildren(temp->left);
        replaceParentWithSumOfChildren(temp->right);
     
        if(temp->left != NULL && temp->right == NULL)
        {
            temp->info = temp->left->info;
            if(temp->left->left == NULL && temp->left->right == NULL)
                temp->left->info = 0;
        }
        else if(temp->right != NULL && temp->left == NULL)
        {
            temp->info = temp->right->info;
            if(temp->right->left == NULL && temp->right->right == NULL)
                temp->right->info = 0;
        }
        else if(temp->left != NULL && temp->right != NULL)
        {
            temp->info = temp->left->info + temp->right->info;
            if(temp->right->left == NULL && temp->right->right == NULL)
                temp->right->info = 0;
            if(temp->left->left == NULL && temp->left->right == NULL)
                temp->left->info = 0;
        }
    }
    else
        return;
}