Convert a Binary Tree to its Sum Tree

• Write a C program to convert a binary tree to sum tree.
• Write a recursive function in C to build a sum tree

Given a binary tree of integers, we have to convert binary tree to a Sum tree. A sum tree is a binary tree where each node is equal to the sum of left sum tree and right sub tree of original tree. Remember, in sum tree each node only contains the sum of nodes in both sub tree not it's own value. The value of each leaf node will become to 0, as they don't have any sub tree.

---

Algorithm to covert a binary tree to sum tree.
Let "node" be the pointer to any node of binary tree while traversing.

• If node is equal to NULL, then return 0.
• Store the value of node in a temporary variable.Let it be temp.
• Recursively, calculate the sum the nodes in left and right sub tree. let it be leftSum and rightSum.
• Set the value of node to leftSum + rightSum.
• Return the sum of all the nodes of sub tree rooted at node. Return temp + leftSum + rightSum.

Time Complexity : O(n) where n is the number of nodes in a binary tree. We are just traversing each node of binary tree.

---

In this program, we will write a function called "buildSumTree" which takes a root of a binary tree as input and convert it to sum tree by implementing above mentioned algorithm.

int buildSumTree(struct node *nodePtr) {
    /* Recursion termination condition */
    if(nodePtr == NULL)
      return 0;
 
    /* Store the original value of a node in a temp variable */
    int temp = nodePtr->data;
 
    /* Recursively calculates the sum of all nodes of left and right sub-tree */
    nodePtr->data = buildSumTree(nodePtr->left) + buildSumTree(nodePtr->right);
 
    /* Return the sum of all nodes of a sub tree whose root node is nodePtr*/
    return nodePtr->data + temp;
}

C program to convert a binary tree to sum tree

#include <stdio.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \    \
       4  5    7
      / \
     8  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->right = getNewNode(7);
 
    root->left->left->left = getNewNode(8);
    root->left->left->right = getNewNode(9);
    
    return root;

}

int buildSumTree(struct node *nodePtr) {
    /* Recursion termination condition */
    if(nodePtr == NULL)
      return 0;
 
    /* Store the original value of a node in a temp variable */
    int temp = nodePtr->data;
 
    /* Recursively calculates the sum of all nodes 
       of left and right sub-tree */
    nodePtr->data = buildSumTree(nodePtr->left) 
                       + buildSumTree(nodePtr->right);
 
    /* Return the sum of all nodes of a sub 
       tree whose root node is nodePtr*/
    return nodePtr->data + temp;
}

void printInorder(struct node *nodePtr){
 if(nodePtr == NULL)
     return;
 printInorder(nodePtr->left);
 printf(" %d", nodePtr->data);
 printInorder(nodePtr->right);
 
}

int main() {
    struct node *root = generateBTree();    
    
    /* Building a SumTree  */
    buildSumTree(root);
    /* printing INorder traversal of Sum Tree */
   printInorder(root);
    
    getchar();
    return 0; 
}

Output

 0 17 0 26 0 38 7 0