Domain 1EasyCORE

Sum of Root To Leaf Binary Numbers

The problem requires us to find the sum of all root-to-leaf binary numbers in a binary tree where each node has a value of either 0 or 1. A root-to-leaf path represents a binary number starting from the most significant bit at the root and ending at the leaf node.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree

1022. Sum of Root To Leaf Binary Numbers

Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 71.6%


Problem Breakdown

The problem requires us to find the sum of all root-to-leaf binary numbers in a binary tree where each node has a value of either 0 or 1. A root-to-leaf path represents a binary number starting from the most significant bit at the root and ending at the leaf node.

Inputs:

  • root: The root node of a binary tree with nodes having values 0 or 1.

Outputs:

  • An integer representing the sum of all root-to-leaf binary numbers.

Implicit Constraints/Edge Cases:

  • The tree can be empty, but since the problem guarantees at least one node, we don’t need to handle an empty tree.
  • Each node value is either 0 or 1, so no other values are possible.
  • The result is guaranteed to fit in a 32-bit integer.

Intuition

A brute-force approach would involve generating all root-to-leaf paths, converting each path to its binary number equivalent, and summing these numbers. However, this approach would be inefficient in terms of both time and space complexity, especially for large trees.

The key insight is to use a depth-first search (DFS) traversal to accumulate the binary number as we traverse from the root to each leaf node. This way, we avoid generating all paths explicitly and can compute the sum directly during the traversal.

Approach

We will use a recursive DFS approach to traverse the tree. As we traverse down the tree, we maintain a running total of the current binary number formed by the path from the root to the current node. When we reach a leaf node, we add this accumulated value to the final sum.

  1. Start at the root with an initial value of 0.
  2. For each node, update the current value by shifting it left (equivalent to multiplying by 2) and adding the node’s value.
  3. If the node is a leaf (i.e., it has no left or right children), add the current value to the sum.
  4. Recursively apply this process to the left and right children of the current node.
  5. Return the total sum after traversing all paths.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
  • Space Complexity: O(h), where h is the height of the tree. This is due to the recursion stack. In the worst case, for a skewed tree, this could be O(n).

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def sumRootToLeaf(root: TreeNode) -> int:
    def dfs(node: TreeNode, current_value: int) -> int:
        if not node:
            return 0
        
        # Update the current value by shifting left and adding the node's value
        current_value = (current_value << 1) | node.val
        
        # If it's a leaf node, return the current value
        if not node.left and not node.right:
            return current_value
        
        # Recursively sum the values of left and right subtrees
        return dfs(node.left, current_value) + dfs(node.right, current_value)
    
    return dfs(root, 0)

# Example usage:
# root = TreeNode(1, TreeNode(0, TreeNode(0), TreeNode(1)), TreeNode(1, TreeNode(0), TreeNode(1)))
# print(sumRootToLeaf(root))  # Output: 22

Edge Cases Handled

  • Single Node Tree: If the tree consists of only one node with value 1, the output will be 1.
  • All Zeros Path: If all paths from root to leaf consist entirely of zeros, the sum will be zero.
  • Balanced vs Skewed Trees: The solution handles both balanced and skewed trees efficiently due to its recursive nature.