Tree  Sum Root to Leaf Numbers
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
PreOrder DFS
Problem
You are given the root
of a binary tree containing digits from 0
to 9
only. Each roottoleaf path in the tree represents a number.
 For example, the roottoleaf path
1 > 2 > 3
represents the number123
.
Return the total sum of all roottoleaf numbers. Test cases are generated so that the answer will fit in a 32bit integer. A leaf node is a node with no children.
Example 1:
1
2
3
4
5
6
Input: root = [1,2,3]
Output: 25
Explanation:
The roottoleaf path 1>2 represents the number 12.
The roottoleaf path 1>3 represents the number 13.
Therefore, sum = 12 + 13 = 25.
Example 2:
1
2
3
4
5
6
7
Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The roottoleaf path 4>9>5 represents the number 495.
The roottoleaf path 4>9>1 represents the number 491.
The roottoleaf path 4>0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.
Solution
Let’s start with the visualization of the solution.

Base Condition: Return
0
forNone
nodes.
The base condition is not needed if all the nodes in the tree has a
left
andright
nodes as in case of that the 2nd base (explained below) will be returned andNone
node will never occur. Here is an example. 
However if in case there are nodes with only one child (
left
orright
), we need to validateif root is None
andreturn 0
as base case. Here is an example.

Everytime we find a new root node (either by traversing
left
orright
child), we need to multiply the previous number by10
and then add currentroot.val
. [e.g4 > 40+9
,49> 490+5
]2nd Base Case : Once we reach a node with no leaf nodes (
left
orright
), we shall return thenum
value. This is the 2nd base case [Terminating condition].At each
node
level we sum the restured value by traversingleft
&right
child values. [e.g495 + 491 = 986
,986 + 40 = 1026
]
The typical flow of the dfs()
function looks like this.
flowchart TD
Z["dfs()"]
Z>A
A["Base Condition"]
Z>B["Sum to New Number"]>D["Return sum if leaf node"]
C["Traverse Left and Right Nodes"]
B>C
A>K[Return 0]
C>M["Return Sum"]
Base Condition
The base condition if there are nodes with only one child (left
or right
). Then that child needs to return just 0
as num.
1
2
if not root:
return 0
Sum to New Number
Calculare new number.
1
2
3
4
def dfs(root, sum_from_root):
if not root:
return 0
new_sum = sum_from_root * 10 + root.val
Return sum if leaf node
Once we reach a node with no leaf nodes (left
or right
), we shall return the num
value. This is the 2nd terminating condition.
1
2
if not root.left and not root.right:
return new_sum
Traverse (Add)
Now traverse through left
and right
children. The only logic here to sum
the returns. The sum
is bit complicated to understand and thats the only reason the problem is medium in LeetCode.
Except at the leaf level, at all other levels, the two sum of two nodes will be added. (Please refer the diagram below). So conversely every node except the leaf nodes, combines sum from two leaf nodes.
So, to achieve 111+112+113+114 = 450
, we calculate (111+112)=223, (113+114)=227
, then combine 223 + 227 = 450
.
1
return dfs(root.left,new_sum)+dfs(root.right,new_sum)
Finally we can call the dfs()
function for the first time by passing the root
node 0
as initial value of num
.
1
return dfs(root,0)
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def sum_numbers(root:TreeNode):
def dfs(root, sum_from_root):
if not root:
return 0
new_sum=sum_from_root*10+root.val
if not root.left and not root.right:
return new_sum
return dfs(root.left,new_sum)+dfs(root.right,new_sum)
return dfs(root,0)