[Programming Problem] Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only.
 
Each root-to-leaf path in the tree represents a number.
 
For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.
Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.
 
A leaf node is a node with no children.
 
Example 1:
Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
 
 
Example 2:
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Problem Link

Use a recursive algorithm to keep traversing tree, while building the path. Once you reach a leaf node calculate the sum(path + leaf node) and store it in the totalSum.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function(root) {
    const sumRef = [0];
    sum(root, [], sumRef);
    return sumRef[0];
};
 
var sum = function(root, path, sumRef) {
    if (root === null) return;
    if (root.left === null && root.right === null) {
        sumRef[0] += Number(path.join('') + root.val);
        return;
    }
 
    sum(root.left, [...path, root.val], sumRef);
    sum(root.right, [...path, root.val], sumRef);
}

8 thoughts on “[Programming Problem] Sum Root to Leaf Numbers

  1. Really? It really is excellent to witness anyone ultimate begin addressing this stuff, however I?m still not really certain how much I agree with you on it all. I subscribed to your rss feed though and will certainly keep following your writing and possibly down the road I may chime in once again in much more detail good work. Cheers for blogging though!

  2. I intended to create you a little remark to finally thank you again just for the beautiful thoughts you’ve discussed at this time. It’s incredibly open-handed with you to give publicly all some people might have offered as an e-book to end up making some dough for their own end, notably since you could have tried it if you considered necessary. The points additionally served to become great way to comprehend other people have similar desire much like my very own to find out a whole lot more concerning this issue. I am certain there are thousands of more pleasant periods ahead for people who look over your site.

Leave a Reply

Your email address will not be published.