Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every root-to-node path is a binary prefix. Descending to a child appends one bit, so its value becomes twice the parent's prefix plus the child's value. Only leaves finish complete root-to-leaf numbers.

Approach

Traverse the tree with depth-first search, carrying the prefix value. At each node, shift the prefix left and append the node's bit. Add it to the total only when both children are absent; otherwise recurse into each existing child with the updated prefix. Return the accumulated total after visiting the tree. Passing the numeric prefix separately into each branch prevents sibling paths from sharing partial state.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def dfs(node, b):
            b <<= 1
            b |= node.val

            if not node.left and not node.right:
                self.res += b
                return
            
            if node.left: dfs(node.left, b)
            if node.right: dfs(node.right, b)
        
        dfs(root, 0)
        return self.res

Complexity analysis

For N nodes and tree height H, both DFS traversals take O(N) time and O(H) auxiliary recursion space. The stated guarantee that the nonnegative root-to-leaf sum fits a signed 32-bit integer also bounds every carried prefix, so JavaScript's bitwise operations are safe here. An allowed 1000-node chain can nevertheless exceed Python's runtime recursion limit.