transform-to-sum-tree.md

Transform to Sum Tree

Given a Binary Tree of size N , where each node can have positive or negative values. Convert this to a tree where each node contains the sum of the left and right sub trees of the original tree. The values of leaf nodes are changed to 0.

Sample Input

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

Sample Output

        20
      /    \
    4        12
   /  \     /  \
 0     0   0    0

Solution

class Solution {
  public:
    int createSumTree(Node *node) {
        
        if(node == NULL) return 0;
        
        int left = createSumTree(node->left);
        int right = createSumTree(node->right);
        int temp = node->data;
        node->data = left + right;
        
        return (left + right + temp);
    }
    
    void toSumTree(Node *node)
    {
       createSumTree(node);
    }
};

Accepted