[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);
}

softwareeveryday

578 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!

    Reply

  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.

    Reply

  11. I must show my gratitude for your generosity for people that really need guidance on your field. Your very own commitment to passing the message all-around ended up being unbelievably effective and has frequently enabled guys and women like me to get to their pursuits. Your new insightful facts can mean a great deal a person like me and additionally to my mates. Many thanks; from all of us.

    Reply

  12. I simply needed to appreciate you again. I am not sure the things that I could possibly have implemented without the strategies contributed by you regarding such a problem. It absolutely was a real scary difficulty for me personally, nevertheless seeing the very skilled avenue you solved the issue forced me to weep for gladness. I will be happier for your work as well as sincerely hope you really know what an amazing job you’re putting in educating people today by way of your websites. Most probably you haven’t come across any of us.

    Reply

  13. I must point out my passion for your generosity for individuals that should have assistance with that study. Your special dedication to passing the solution all around ended up being especially practical and has all the time permitted associates much like me to realize their endeavors. Your important useful information implies this much to me and still more to my office workers. Thank you; from everyone of us.

    Reply

  14. I want to voice my respect for your kind-heartedness in support of folks who require guidance on that idea. Your real commitment to getting the solution all around had been incredibly beneficial and has usually helped girls much like me to achieve their ambitions. Your amazing useful report implies a whole lot to me and much more to my peers. Thanks a lot; from everyone of us.

    Reply

  17. Needed to send you one little bit of observation just to say thanks a lot again just for the pleasant views you’ve shared here. This is certainly particularly open-handed with you to present unhampered just what many people could have marketed for an electronic book to get some cash for themselves, precisely considering that you could possibly have done it in case you wanted. The points as well acted like a easy way to realize that many people have the same dream the same as mine to realize way more concerning this issue. I’m sure there are many more pleasurable opportunities up front for individuals who find out your site.

    Reply

  18. I want to express my admiration for your kind-heartedness supporting men who have the need for guidance on this one niche. Your personal commitment to passing the solution all through appeared to be especially powerful and has always empowered men and women just like me to arrive at their targets. Your new useful tips and hints signifies a great deal to me and somewhat more to my peers. Thanks a lot; from all of us.

    Reply

  21. I want to convey my affection for your kind-heartedness supporting those people who really need help on this one theme. Your special commitment to getting the message up and down ended up being extremely invaluable and have really encouraged somebody just like me to get to their desired goals. Your new helpful facts implies much to me and substantially more to my colleagues. Warm regards; from everyone of us.

    Reply

  32. I would like to point out my passion for your kind-heartedness giving support to folks who must have help with in this question. Your special dedication to getting the solution along was really beneficial and have surely encouraged workers like me to realize their objectives. Your new useful guideline can mean a lot to me and especially to my colleagues. With thanks; from each one of us.

    Reply

  87. Thanks a lot for giving everyone remarkably splendid possiblity to read from here. It is always so superb and also full of fun for me and my office fellow workers to visit your website at the very least three times per week to see the fresh secrets you will have. And definitely, I’m so actually astounded concerning the beautiful secrets served by you. Selected two tips on this page are ultimately the most suitable we have ever had.

    Reply

  94. I wish to convey my appreciation for your kind-heartedness supporting folks who absolutely need help on the area of interest. Your very own commitment to passing the solution all through appears to be unbelievably functional and has permitted women much like me to get to their endeavors. Your amazing insightful publication implies a lot a person like me and even more to my mates. Warm regards; from everyone of us.

    Reply

  98. I intended to put you a bit of word in order to give many thanks yet again regarding the striking pointers you’ve discussed above. It was really incredibly generous of people like you to convey easily all some people could possibly have supplied as an e-book to end up making some bucks for themselves, primarily seeing that you could have done it in case you wanted. Those tricks as well acted to become good way to be sure that someone else have the identical interest much like my very own to figure out somewhat more with respect to this problem. Certainly there are some more pleasant opportunities ahead for those who read carefully your site.

    Reply

  117. I simply had to appreciate you again. I am not sure what I might have followed without the actual opinions documented by you regarding this topic. It previously was the intimidating scenario in my position, however , seeing the very specialized manner you processed it made me to weep for happiness. I am happier for your support and even believe you know what a powerful job you’re putting in training others with the aid of your website. More than likely you haven’t got to know any of us.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

[Programming Problem] Subsets II
Read More
[Programming Problem] Flatten Binary Tree to Linked List
Read More
[Programming Problem] Largest Number
Read More