Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.

The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Recursive solution:

The idea is for each recursive node, calculate its left subtree path sum + right subtree path sum.

public int sumNumbers(TreeNode root) {
        if (root==null) {
            return 0;
        }

        return sumNumber(root, 0);
    }

    public int sumNumber(TreeNode root, int number) {
        //if leaf node, return the final path integer
        if (root.left==null && root.right==null) {
            return number*10 + root.val;
        }

        int leftVal = 0;
        int rightVal = 0;

        if (root.left!=null) {
            leftVal = sumNumber(root.left, number*10+root.val);
        }

        if (root.right!=null) {
            rightVal = sumNumber(root.right, number*10+root.val);
        }
        return leftVal + rightVal;
    }

Iterative solution:

Apply binary tree level order traversal logic, use another queue to track for a given node the path sum from root to its left child and right child. When you see a leaf node, add the sum to the final results.

public int sumNumbersIter(TreeNode root) {
        if (root==null) {
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        Queue<Integer> results = new LinkedList<Integer>();
        queue.add(root);
        results.add(root.val);

        int sumResult = 0;
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            int sum = results.poll();

            if (current.left!=null) {
                queue.add(current.left);
                results.add(sum*10+current.left.val);
            }

            if (current.right!=null) {
                queue.add(current.right);
                results.add(sum*10+current.right.val);
            }

            //add the leaf path sum together
            if (current.left==null&&current.right==null) {
                sumResult += sum;
            }
        }

        return sumResult;
    }