DSA 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 path 1 → 2 → 3 represents the number 123. Return the total sum of all root-to-leaf numbers.
A leaf is a node with no children. The test cases are guaranteed so that the total sum fits within a 32-bit signed integer, so you do not need to worry about overflow.
The natural approach carries a running number down the tree. At every node we update cur = cur * 10 + node.val, which is the standard "shift left in base 10 and append a digit" trick. When we reach a leaf, the running number is exactly the value formed by the path from the root, so we add it to the running total.
The traversal can be coded as a DFS that takes the running number as a parameter, or as a post-order recursion that returns the partial sum from each subtree given the running prefix. Either form visits every node once, performs constant arithmetic per node, and uses O(h) stack space for the recursion. Total complexity: O(n) time and O(h) space.
Examples
root = [1,2,3]25root = [4,9,0,5,1]1026root = [1]1Constraints
- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 9
- The depth of the tree will not exceed 10.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.