Convert a given tree to its Sum Tree

Convert a given tree to its Sum Tree | GeeksforGeeks
Given a Binary Tree where each node has positive and negative values. Convert this to a tree where each node contains the sum of the left and right sub trees in the original tree. The values of leaf nodes are changed to 0.

For example, the following tree

                  10
               /      \
      -2        6
           /   \      /  \ 
  8     -4    7    5

should be changed to

                 20(4-2+12+6)
               /      \
    4(8-4)      12(7+5)
           /   \      /  \ 
  0      0    0    0

Sore the old value of the current node, recursively call for left and right subtrees and change the value of current node as sum of the values returned by the recursive calls. Finally return the sum of new value and value (which is sum of values in the subtree rooted with this node).

    int toSumTree(Node node)

    {

        // Base case

        if (node == null)

            return 0;

  

        // Store the old value

        int old_val = node.data;

  

        // Recursively call for left and right subtrees and store the sum

        // as new value of this node

        node.data = toSumTree(node.left) + toSumTree(node.right);

  

        // Return the sum of values of nodes in left and right subtrees

        // and old_value of this node

        return node.data + old_val;

    }

http://algorithms.tutorialhorizon.com/convert-binary-tree-to-its-sum-tree/

1. Recur­sively cal­cu­late the left sum from left sum tree.
2. Recur­sively cal­cu­late the right sum from right tree.
3. pre­pare the return root.data + left sum + right sum.
4. Update the root data as root.data = left sum + right sum.
5. update the new­Root = root.

  public int SumTree(Node root){
    if(root!=null){
      int left = SumTree(root.left);//take the left tree sum
      int right = SumTree(root.right);//take the right tree sum
      int retData = root.data+left+right; // return data left+right+root
      root.data = left+right; //update the root with left + right
      newRoot = root; //update the new root
      return retData; //return
    }
    return 0;
 }
http://sudhansu-codezone.blogspot.com/2012/01/check-if-given-binary-tree-is-sumtree.html
Question 2:Convert sum 
//Bottom Up approach
int toSumTree(struct node *node)
{
    if(node == NULL)
      return 0;

    int old_val = node->data;

    node->data = toSumTree(node->left) + toSumTree(node->right);

    return node->data + old_val;
}

Top Down approach:

We will go down the tree ach time to calculate sum of sub tree rooted at that node 
int sum(struct node *root)
{
   if(root == NULL)
     return 0;
   return sum(root->left) + root->data + sum(root->right);
}

int isLeaf(struct node *node)
{
    if(node == NULL)
        return 0;
    if(node->left == NULL && node->right == NULL)
        return 1;
    return 0;
}

void StoreSum(struct node*& node)
{
    int ls, rs;
    if(isLeaf(node))
      {   node->data=0;
          return;}
   
    if(node == NULL )
          return;

   ls = sum(node->left);
   rs = sum(node->right);
   node->data = ls + rs;
    StoreSum(node->left);
    StoreSum(node->right);
} 
http://www.dsalgo.com/2013/02/BinaryTreeSumChildNodes.php.html
Read full article from Convert a given tree to its Sum Tree | GeeksforGeeks