Sum of Root To Leaf Binary Numbers

Difficulty: Easy | Acceptance: 76.60% | Paid: No Topics: Tree, Depth-First Search, Binary Tree

You are given the root of a binary tree where each node has a value 0 or 1. Each root-to-leaf path represents a binary number starting with the most significant bit.

For example, if the path is 0 -> 1 -> 1 -> 0 -> 1, then this could represent 01101 in binary, which is 13.

For all leaves in the tree, consider the numbers represented by the path from the root to that leaf. Return the sum of these numbers.

The test cases are generated so that the answer fits in a 32-bit integer.

• Examples
• Constraints
• Recursive DFS
• Iterative DFS
• BFS (Level Order)
• Morris Traversal

Examples

Example 1:

Input: root = [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

Example 2:

Input: root = [0]
Output: 0

Constraints

The number of nodes in the tree is in the range [1, 1000].
Node.val is 0 or 1.

Recursive DFS

Intuition We traverse the tree using Depth-First Search. As we go down from parent to child, we update the current binary number by shifting bits left (multiplying by 2) and adding the current node’s value. When we reach a leaf node, we add the accumulated value to the total sum.

Steps

• Define a helper function that takes a node and the current value accumulated from its parents.
• If the node is null, return 0.
• Update the current value: current = current * 2 + node.val.
• If the node is a leaf (both children are null), return the current value.
• Otherwise, recursively sum the results of the left and right subtrees.

# 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:
        def dfs(node, curr):
            if not node:
                return 0
            curr = (curr << 1) | node.val
            if not node.left and not node.right:
                return curr
            return dfs(node.left, curr) + dfs(node.right, curr)
        return dfs(root, 0)

Complexity

• Time: O(N) where N is the number of nodes, as we visit each node once.
• Space: O(H) where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this is O(N).
• Notes: This is the most intuitive approach for tree problems involving paths.

Iterative DFS

Intuition We simulate the recursion using an explicit stack. This avoids the overhead of recursive calls and potential stack overflow issues for very deep trees (though constraints are small here). We store pairs of (node, current_value) in the stack.

Steps

• Initialize a stack with (root, 0).
• While the stack is not empty:
  • Pop a (node, val) pair.
  • Update the value: val = val * 2 + node.val.
  • If the node is a leaf, add val to the total sum.
  • Push the right and left children onto the stack with the updated val (if they exist).

# 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:
        stack = [(root, 0)]
        total = 0
        while stack:
            node, curr = stack.pop()
            if not node:
                continue
            curr = (curr << 1) | node.val
            if not node.left and not node.right:
                total += curr
            else:
                stack.append((node.right, curr))
                stack.append((node.left, curr))
        return total

Complexity

• Time: O(N) as we process each node exactly once.
• Space: O(H) for the stack. In the worst case, this is O(N).
• Notes: Iterative approach is useful when recursion depth might be a concern, though for N=1000 it is negligible.

BFS (Level Order)

Intuition We process nodes level by level using a queue. Similar to DFS, we carry the current path value along with the node. This ensures we process nodes in order of their depth.

Steps

• Initialize a queue with (root, 0).
• While the queue is not empty:
  • Dequeue a (node, val) pair.
  • Update the value: val = val * 2 + node.val.
  • If the node is a leaf, add val to the total sum.
  • Enqueue the left and right children with the updated val (if they exist).

# 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
from collections import deque

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        q = deque([(root, 0)])
        total = 0
        while q:
            node, curr = q.popleft()
            if not node:
                continue
            curr = (curr << 1) | node.val
            if not node.left and not node.right:
                total += curr
            else:
                q.append((node.left, curr))
                q.append((node.right, curr))
        return total

Complexity

• Time: O(N) as we visit every node once.
• Space: O(W) where W is the maximum width of the tree. In the worst case (complete binary tree), this is O(N).
• Notes: Uses more memory than DFS for deep trees but is useful for level-order processing.

Morris Traversal

Intuition Morris Traversal allows us to traverse the tree in O(1) extra space (excluding the output) by temporarily modifying the tree structure (creating “threads” from the rightmost node of the left subtree back to the current node). We adapt this to maintain the current path value.

Steps

• Initialize curr = root, currSum = 0, total = 0.
• While curr is not null:
  • If curr has no left child:
    • Update currSum = currSum * 2 + curr.val.
    • If curr is a leaf (no right child), add currSum to total.
    • Move to curr.right.
  • Else:
    • Find the inorder predecessor pred (rightmost node in curr’s left subtree).
    • If pred.right is null:
      • Create a thread: pred.right = curr.
      • Update currSum = currSum * 2 + curr.val (we are visiting curr for the first time).
      • Move to curr.left.
    • If pred.right is curr:
      • Break the thread: pred.right = null.
      • Move to curr.right. (Note: currSum is already correct for curr, so we don’t update it here before moving right).

# 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:
        total = 0
        curr_sum = 0
        curr = root
        
        while curr:
            if not curr.left:
                curr_sum = (curr_sum << 1) | curr.val
                if not curr.right:
                    total += curr_sum
                curr = curr.right
            else:
                pred = curr.left
                while pred.right and pred.right != curr:
                    pred = pred.right
                
                if not pred.right:
                    pred.right = curr
                    curr_sum = (curr_sum << 1) | curr.val
                    curr = curr.left
                else:
                    pred.right = None
                    curr = curr.right
        return total

Complexity

• Time: O(N) as each node is visited a constant number of times.
• Space: O(1) extra space (ignoring recursion stack and input storage), as we modify the tree temporarily.
• Notes: This is an advanced technique useful when space complexity is a strict constraint. It modifies the tree structure during traversal but restores it afterwards.