Sum of Binary Tree Nodes

For the past few days i have been digging into the Trees Data Structure. Trees or graphs are one the most practically used Data Structure due to their better performance over Linked list and Arrays.

Let's go straight to the problem: We need to calculate the sum for all the parent nodes in the tree and only leaf nodes has the values.

Thanks to this post Post on stackoverflow, this issue is a problem of recursion. Remember for any issue where you need to travel each node in a tree can be solved by recursion. If you want to traverse a tree (In order, Preorder or Post Order) you will use recursion to do this.

Example Tree :


-------------------------------------------------------------
                                5,0,0                                                            
                3,0,0                              7,0,0                            
        2,0,0              4,0,0              6,0,0              9,0,0            
-------------------------------------------------------------

This is the Node class which i have printed


public class TreeNodeLL {

int key;
int data;
int leftSum;
int rightSum;
TreeNodeLL leftChild;
TreeNodeLL rightChild;

public TreeNodeLL(int key, int data) {
this.key = key;
this.data = data;
this.leftChild = null;
this.rightChild = null;
}

}

So the leftSum = Sum of 'key' variable in the left Sub-tree.
similarly rightSum = Sum of 'key' variable in Right Sub-tree.




We have the method to calculate this



public int sum(TreeNodeLL node){
if (node == null) {
return 0;
}
else{
node.leftSum = sum(node.leftChild);
node.rightSum = sum(node.rightChild);
return node.key + node.leftSum + node.rightSum;
}
}

Output would be:


-------------------------------------------------------------
                                5,9,22                                                            
                3,2,4                              7,6,9                            
        2,0,0              4,0,0              6,0,0              9,0,0            
-----------------------------------------------------------



References:
Data Structures in Java by Robert Lafore
Stackoverflow.com