Replace the data of each node by the sum of data of all its descendent nodes

Question :

Given a Binary Tree, replace the data of each node by the sum of data of all its descendent nodes.(Leaf nodes will have 0)

 Solution : 

The solution is simple recursive one.  For each node you need to set value of the node equal to the sum of value of it's left and right node. Each sub node will in turn calculate their value and based on sum of their children and return the sum with it's original value added.

Before providing the solution lets view the problem graphically

Before we process the tree lets say it is something like below

 The final result we are interested is 

Lets write the code for it. Note the code for Node data structure as well as various traversals is provided in this post which was poster earlier. There is a slight modification that we are adding and int value instance variable along with its getters ans setters. There is corresponding change in the constructor but the logic remains same.

Code : 

package in.blogspot.osg.Demo;

public class ReplaceWithDescendantSum {
    
    public static int replace(Node root){
        
        int rightValue = 0;
        int leftValue = 0 ;
        
        if(root.getRight() != null)
            rightValue = replace(root.getRight());
        if(root.getLeft() != null)
            leftValue = replace(root.getLeft());
        
        int sumOfDesendants = rightValue + leftValue;
        int retunValue = root.getValue() + sumOfDesendants;
        root.setValue(sumOfDesendants);
        return (retunValue);
        
    }

}

Above code will do the job.

 Lets write the main() method to test this out.

    public static void main(String args[]){
        
        Node root = new Node(1);
        Node l = new Node(2);
        Node r = new Node(3);
        
        Node l1 = new Node(12);
        Node l2 = new Node(13);
        
        Node r1 = new Node(6);
        Node r2 = new Node(8);
        
        root.setLeft(l);
        root.setRight(r);
        
        l.setLeft(l1);
        l.setRight(l2);
        
        r.setLeft(r1);
        r.setRight(r2);
        
        System.out.println("***Before***");
        PreOrder.printPreOrder(root);
        ReplaceWithDescendantSum.replace(root);
        System.out.println("**After**");
        PreOrder.printPreOrder(root);
        
    }

Output : 

 

***Before***
Value : 1
Value : 2
Value : 12
Value : 13
Value : 3
Value : 6
Value : 8
**After**
Value : 44
Value : 25
Value : 0
Value : 0
Value : 14
Value : 0
Value : 0