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.

Approach:

The problem can be solved recursively with post-order traversal (left-right-root), as we need the values of child nodes before updating the current node.

?? View Full Code ??

Steps:

• Use a recursive function to compute and update each node.
• For each node, recursively calculate the sum of its left and right subtrees.
• Store the original node value before updating.
• Update the node’s value to the sum of the left and right subtrees.
• Return the sum of the original node’s value plus the subtree sum (for parent nodes' calculations).
• If a node is NULL, return 0.
• For leaf nodes, update the node’s value to 0.

int solve(Node* node){
        
        if(node == NULL) return 0;
        
        int left = solve(node->left);
        int right = solve(node->right);
        
        int originalValue = node->data;
        
        node->data = left+right;
        
        return originalValue + node->data;

    }
    
    void toSumTree(Node *node)
    {
        solve(node);   
    }        

Time Complexity: O(N)

Space Complexity: O(N)

where N is number of nodes

?? GitHub Repo??