Each root to leaf path in a tree of digits forms a number. Return the sum of all these numbers.
DSA Animator › DSA Revision › Tree › Sum Root to Leaf Numbers
Remember: times 10 plus the digit builds the number on the way down. Leaves return numbers, and parents add them up. The video solves Sum Root to Leaf Numbers (LeetCode 129, Medium) with the DFS Carry Value pattern from the Tree topic, and you can replay every step in the interactive Sum Root to Leaf Numbers animation.
Each root to leaf path in a tree of digits forms a number. Return the sum of all these numbers.
For the tree 4, with children 9 and 0, where 9 has children 5 and 1, the numbers are 495, 491 and 40. Their sum is 1026.
You could build each path as a string and convert it at the leaf. Carrying the number as an integer is simpler and faster.
Carry the number formed so far, starting from 0. At each node, multiply it by 10 and add the node digit. At a leaf, that is one complete number, so return it. At other nodes, return the sum of the left and right results.
At 4, the number is 4. At 9, it becomes 49. At the leaf 5, it becomes 495, and at the leaf 1, it becomes 491. So the subtree of 9 returns 986. At the leaf 0, the number is 40. The root returns 986 plus 40, which is 1026.
In code, the helper takes a node and the current number. Return 0 for null, and update the number as current times 10 plus the value. If it is a leaf, return the number. Otherwise return the left sum plus the right sum, so it's O of n time.
Remember: times 10 plus the digit builds the number on the way down. Leaves return numbers, and parents add them up.