Sum of Root to Leaf Binary Numbers
January 9, 2024
Problem #
Given a binary tree where each node can either be 0 or 1, each roottoleaf path represents a binary number. A leaf is a node with no children. The root is the top node of the tree. Calculate the sum of these numbers.
Example: #

Input:
1 / \ 0 1 / \ / \ 0 1 0 1
Output: 22
Explanation: The binary numbers are 100, 101, 110, and 111, which sum to 22.
Solution Approach #
The solution involves a depthfirst search (DFS) from the root to each leaf, keeping track of the current number. When a leaf is reached, add its value to the total sum.
Algorithm Steps #
 Define a helper function
dfs
that takes a node and the current value.  In
dfs
, check if the node is a leaf. If yes, return its value.  Recursively call
dfs
for left and right children, updating the current value by shifting it left (multiply by 2) and adding the node’s value.  Start
dfs
from the root and accumulate the sum of all leaf values.  Return the total sum.
Code (Python) #
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sumRootToLeaf(root):
def dfs(node, curr_val):
if not node:
return 0
curr_val = curr_val * 2 + node.val
if not node.left and not node.right:
return curr_val
return dfs(node.left, curr_val) + dfs(node.right, curr_val)
return dfs(root, 0)
# Example tree construction and test
root = TreeNode(1)
root.left = TreeNode(0, TreeNode(0), TreeNode(1))
root.right = TreeNode(1, TreeNode(0), TreeNode(1))
print(sumRootToLeaf(root)) # Output: 22
Time Complexity #
The time complexity is O(n), where n is the number of nodes in the tree, as we visit each node once.
Space Complexity #
The space complexity is O(h), where h is the height of the tree, due to the recursion stack in the DFS.