LeetCode 1022 Explained: DFS Approach in Python

In LeetCode 1022. Sum of Root To Leaf Binary Numbers, you are given a binary tree where every node contains either 0 or 1. Each root-to-leaf path forms a binary number when you read the node values from the root (most significant bit) to the leaf (least significant bit). Your task is to return the sum of all these binary numbers in decimal.

---

Key idea

Instead of building strings like "1011" for every path, you can build the number efficiently while traversing the tree.

When you move from a node to its child, you are appending one binary digit to the end of the current number:

• Shift left by 1 (multiply by 2)
• Add the new bit (0 or 1)

So, if the current value is curr and the new node bit is node.val, then:

• curr = (curr << 1) | node.val

This single line is the core of the solution.

---

Strategy

Use DFS (Depth-First Search) and carry the running binary value down the recursion:

1. Start at the root with curr = 0
2. Update curr at every node using shifting and OR
3. When you reach a leaf, that curr represents one complete root-to-leaf binary number
4. Return the sum of all leaf values

---

Time and space complexity

• Time: O(N) — every node is visited once
• Space: O(H) — recursion stack, where H is the height of the tree

---

Python solution

# 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):
        def dfs(node, curr):
            if not node:
                return 0

            # Append this bit to the running binary number
            curr = (curr << 1) | node.val

            # If leaf node, return the number formed by this path
            if not node.left and not node.right:
                return curr

            # Sum from left and right subtrees
            return dfs(node.left, curr) + dfs(node.right, curr)

        return dfs(root, 0)

---

Quick example walkthrough

For a path 1 → 0 → 1:

• Start: 0
• After 1: (0<<1)|1 = 1 (binary 1)
• After 0: (1<<1)|0 = 2 (binary 10)
• After 1: (2<<1)|1 = 5 (binary 101)

At the leaf, add 5 to the total.