Problem Description

You have a binary tree where each node contains either a value of 0 or 1.

Each path from the root node to a leaf node represents a binary number. The binary number is formed by reading the node values along the path from top to bottom, where the root node's value is the most significant bit.

For example, if you traverse a path with values 0 -> 1 -> 1 -> 0 -> 1, this represents the binary number 01101, which equals 13 in decimal.

Your task is to:

1. Find all root-to-leaf paths in the tree
2. Convert each path to its decimal equivalent
3. Return the sum of all these decimal values

The problem guarantees that the final answer will fit within a 32-bit integer.

Example walkthrough:

• If a path is 1 -> 0 -> 1, the binary number is 101, which equals 5 in decimal
• If another path is 1 -> 1, the binary number is 11, which equals 3 in decimal
• The sum would be 5 + 3 = 8

The solution uses a depth-first search (DFS) approach with bit manipulation. As we traverse down the tree, we build the binary number by shifting the current value left by one position (t << 1) and adding the current node's value using bitwise OR (| root.val). When we reach a leaf node (a node with no children), we add the accumulated binary number to our sum.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a binary tree, which is a special type of graph with nodes (tree nodes) and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a binary tree structure where we need to traverse from root to leaf nodes.

DFS

• We arrive at DFS: Since we're dealing with a tree and need to explore complete paths from root to leaf nodes, DFS is the natural choice.

Why DFS is appropriate for this problem:

• We need to traverse complete paths from root to leaf (depth-oriented traversal)
• We need to maintain the current binary number as we go down each path
• DFS allows us to naturally track the path state through recursion or a stack
• When we reach a leaf, we can immediately process the complete binary number
• The recursive nature of DFS makes it easy to accumulate values as we traverse down and automatically backtrack to explore other paths

Conclusion: The flowchart correctly leads us to use DFS for this tree traversal problem. The DFS approach allows us to efficiently explore all root-to-leaf paths while building up the binary numbers incrementally using bit manipulation (t = (t << 1) | root.val), and sum them up when we reach the leaf nodes.

Intuition

When we look at this problem, we need to think about how binary numbers are constructed. In a binary number like 101, each digit represents a power of 2, reading from left to right with decreasing powers. The leftmost digit is the most significant bit.

As we traverse down a path in the tree, we're essentially building a binary number digit by digit. Each time we move to a child node, we're adding a new digit to the right of our current binary number. This is exactly what happens when we shift a binary number left by one position and add a new bit.

For example, if we have the binary number 10 (decimal 2) and we encounter a node with value 1, we want to form 101 (decimal 5). We can achieve this by:

1. Shifting 10 left by one position to get 100 (decimal 4)
2. Adding the new bit 1 to get 101 (decimal 5)

This operation can be written as t = (t << 1) | root.val, where << is the left shift operator and | is the bitwise OR operation.

The key insight is that we need to explore every possible root-to-leaf path and calculate its decimal value. DFS is perfect for this because:

• It naturally explores complete paths before backtracking
• We can pass the accumulated binary value as a parameter during recursion
• When we reach a leaf node, we have the complete binary number for that path
• The recursive calls automatically handle the summation of all paths

The beauty of this approach is that we don't need to store the entire path or convert strings to numbers. We build the decimal value incrementally as we traverse, making the solution both elegant and efficient.

Learn more about Tree, Depth-First Search and Binary Tree patterns.

Solution Approach

The solution implements a recursive DFS approach with bit manipulation to efficiently calculate the sum of all root-to-leaf binary numbers.

Core Algorithm Structure:

We define a helper function dfs(root, t) that takes two parameters:

• root: the current node being processed
• t: the accumulated binary number (in decimal) from the root to the current node

Step-by-step Implementation:

1. Base Case - Null Node: If the current node is None, we return 0. This handles the case where we might call DFS on a non-existent child.

2. Build the Binary Number: For each node, we update the accumulated value using bit manipulation:

   t = (t << 1) | root.val

   • t << 1 shifts the current binary number left by one position (equivalent to multiplying by 2)
   • | root.val adds the current node's value as the least significant bit

   For example, if t = 5 (binary 101) and root.val = 1, then:

   • t << 1 gives us 10 (binary 1010)
   • 10 | 1 gives us 11 (binary 1011)

3. Leaf Node Detection: When we reach a leaf node (both root.left and root.right are None), we've completed a root-to-leaf path. We return the accumulated value t, which represents the decimal value of the binary number formed by this path.

4. Recursive Exploration: For non-leaf nodes, we recursively explore both subtrees:

   return dfs(root.left, t) + dfs(root.right, t)

   This automatically sums up the values from all paths in the left and right subtrees.

5. Initial Call: We start the recursion with dfs(root, 0), beginning with an accumulated value of 0.

Why This Works:

The recursive nature of DFS ensures that:

• Each path is explored completely before backtracking
• The binary number is built incrementally as we go deeper
• The sum is accumulated naturally through the recursive returns
• No additional data structures are needed to store paths or intermediate results

The time complexity is O(n) where n is the number of nodes, as we visit each node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursion stack.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Consider this binary tree:

       1
      / \
     0   1
    / \
   0   1

This tree has three root-to-leaf paths:

• Path 1: 1 -> 0 -> 0
• Path 2: 1 -> 0 -> 1
• Path 3: 1 -> 1

Step-by-step DFS traversal:

1. Start at root (value=1):

   • t = 0 (initial value)
   • Update: t = (0 << 1) | 1 = 0 | 1 = 1
   • Not a leaf, so recurse on both children

2. Go left to node (value=0):

   • Current t = 1 (binary: 1)
   • Update: t = (1 << 1) | 0 = 2 | 0 = 2 (binary: 10)
   • Not a leaf, continue recursing

3. Go left again to node (value=0):

   • Current t = 2 (binary: 10)
   • Update: t = (2 << 1) | 0 = 4 | 0 = 4 (binary: 100)
   • This is a leaf! Return 4

4. Backtrack and go right to node (value=1):

   • Current t = 2 (binary: 10)
   • Update: t = (2 << 1) | 1 = 4 | 1 = 5 (binary: 101)
   • This is a leaf! Return 5

5. Backtrack to root and go right to node (value=1):

   • Current t = 1 (binary: 1)
   • Update: t = (1 << 1) | 1 = 2 | 1 = 3 (binary: 11)
   • This is a leaf! Return 3

Final calculation:

• Path 1 -> 0 -> 0 = binary 100 = decimal 4
• Path 1 -> 0 -> 1 = binary 101 = decimal 5
• Path 1 -> 1 = binary 11 = decimal 3
• Total sum = 4 + 5 + 3 = 12

The bit manipulation elegantly builds each binary number:

• Starting with 0, we shift and add bits as we traverse
• (0 << 1) | 1 = 1 gives us the first bit
• (1 << 1) | 0 = 2 adds a zero to get 10
• (2 << 1) | 1 = 5 adds a one to get 101

Each recursive call returns the sum of all paths in its subtree, naturally accumulating the total.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node in the tree is visited exactly once. During each visit, the algorithm performs constant time operations: bit shifting (t << 1), bitwise OR | root.val, and checking if a node is a leaf. Since we visit all n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(n)

The space complexity is determined by the recursion call stack. In the worst case, the tree is completely unbalanced (e.g., a skewed tree where each node has only one child), resulting in a recursion depth equal to the number of nodes n. This would require O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Handling Single-Child Nodes

A frequent mistake is assuming that the recursive calls will naturally handle nodes with only one child, but then accidentally treating single-child nodes as leaf nodes.

Incorrect Implementation:

def dfs(node, current_value):
    if node is None:
        return 0
  
    current_value = (current_value << 1) | node.val
  
    # WRONG: This would treat single-child nodes as leaves
    if node.left is None or node.right is None:
        return current_value
  
    return dfs(node.left, current_value) + dfs(node.right, current_value)

Why it's wrong: A node with only one child is NOT a leaf node. The path must continue to the actual leaf.

Correct Approach:

def dfs(node, current_value):
    if node is None:
        return 0
  
    current_value = (current_value << 1) | node.val
  
    # Only return value if BOTH children are None
    if node.left is None and node.right is None:
        return current_value
  
    return dfs(node.left, current_value) + dfs(node.right, current_value)

2. Using Addition Instead of Bitwise OR

Another common error is using addition (+) instead of bitwise OR (|) when appending the current node's value.

Incorrect Implementation:

# WRONG: This could give incorrect results
current_value = (current_value << 1) + node.val

Why it matters: While this often produces the same result (since we're adding 0 or 1 to an even number after left shift), using bitwise OR is:

• More semantically correct for bit manipulation
• Potentially more efficient
• Clearer in expressing the intent of setting a specific bit

Correct Approach:

# Use bitwise OR to set the least significant bit
current_value = (current_value << 1) | node.val

3. Accumulating the Sum Incorrectly

Some implementations try to use a class variable or pass a mutable object to accumulate the sum, which can lead to complexity and potential bugs.

Problematic Implementation:

class Solution:
    def sumRootToLeaf(self, root):
        self.total = 0  # Class variable approach
      
        def dfs(node, current_value):
            if node is None:
                return
          
            current_value = (current_value << 1) | node.val
          
            if node.left is None and node.right is None:
                self.total += current_value  # Modifying class variable
                return
          
            dfs(node.left, current_value)
            dfs(node.right, current_value)
      
        dfs(root, 0)
        return self.total

Why the recursive return approach is better:

• No need for mutable state or class variables
• More functional and easier to reason about
• Natural accumulation through return values
• Thread-safe if needed

4. Forgetting to Handle Empty Tree

While the problem typically guarantees at least one node, it's good practice to handle the edge case of an empty tree.

Robust Implementation:

def sumRootToLeaf(self, root):
    if root is None:  # Handle empty tree
        return 0
  
    def dfs(node, current_value):
        # ... rest of the implementation
  
    return dfs(root, 0)