Problem Statement

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.

Example 1:

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

Output:
            20
          /    \\
        4        12
       /  \\     /  \\
     0     0   0    0

Problem Link

Transform to Sum Tree | Practice | GeeksforGeeks

Code

/* A binary tree node
struct Node
{
    int data;
    Node* left, * right;
}; */

class Solution {
  public:
  
    // Convert a given tree to a tree where every node contains sum of values of
    // nodes in left and right subtrees in the original tree
    void toSumTree(Node *root)
    {
        solve(root);
    }
    int solve(Node *root)
    {
        if(!root)
        return 0;
        
        if(!root->left&&!root->right)
        {
            int value = root->data;
            root->data = 0;
            return value;
        }
        
        int value = solve(root->left) + solve(root->right);// calculating sum of the values of nodes of lst and rst of a particular parent
        int rdata = root->data; //value at root node
        root->data = value; //replacing the value of root's data with the sum of its lst and rst 
        
        return value+rdata; // passing the value of the subtree to it parent
    }
};