Sum of all the numbers that are formed from root to leaf paths.

Question :

Given a binary tree, where every node value is a Digit from 1-9 .Find the sum of all the numbers which are formed from root to leaf paths.
For example consider the following Binary Tree.

 Solution :

The idea is to do a preorder traversal of the tree. In the preorder traversal, keep track of the value calculated till the current node, let this value be val. For every node, we update the val as val*10 plus node’s data.

Answer is : 632 + 6357 + 6354 + 654 = 13997

 Code :

package Tree;

/**
 * Created by Aniket on 1/24/14.
 */
public class TreePathSummer {

    public static int treePathSum(TreeNode root, int val){

        if(root == null){
            return 0;
        }

        val = val * 10 + root.getData();

        if(root.getLeftNode() == null && root.getRightNode() == null){
            return val;
        }

        return treePathSum(root.getLeftNode(),val) + treePathSum(root.getRightNode(),val);

    }

    public static void main(String args[]){
        TreeNode rooTreeNode = new TreeNode(6);

        TreeNode l = new TreeNode(3);
        TreeNode r = new TreeNode(5);

        TreeNode ll = new TreeNode(2);
        TreeNode lr = new TreeNode(5);

        TreeNode lrl = new TreeNode(7);
        TreeNode lrr = new TreeNode(4);

        TreeNode rr = new TreeNode(4);

        rooTreeNode.setLeftNode(l);
        rooTreeNode.setRightNode(r);

        l.setLeftNode(ll);
        l.setRightNode(lr);

        lr.setLeftNode(lrl);
        lr.setRightNode(lrr);

        r.setRightNode(rr);

        System.out.println("Answer is = " + TreePathSummer.treePathSum(rooTreeNode,0));
    }
}

And the output is as expected

Answer is = 13997

For the java code corresponding to TreeNode data structure refer to the earlier post.