LeetCode 1022 - Sum of Root To Leaf Binary Numbers

This problem gives us the root of a binary tree where every node contains either 0 or 1. Each path from the root node to a leaf node represents a binary number, where the root contributes the most significant bit and each child adds another bit to the right.

leetcodeeasytreedepth-first-searchbinary-tree

LeetCode Problem 1022

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Binary Tree

Solution

Problem Understanding

This problem gives us the root of a binary tree where every node contains either 0 or 1. Each path from the root node to a leaf node represents a binary number, where the root contributes the most significant bit and each child adds another bit to the right.

For example, consider a path:

1 -> 0 -> 1

This represents the binary number 101, which equals 5 in decimal notation.

The task is to compute the sum of all such binary numbers formed by every root-to-leaf path in the tree.

A leaf node is a node with no children. This means we only evaluate complete root-to-leaf paths, not partial paths that stop at internal nodes.

The input is a binary tree represented by its root node. Since every node contains only 0 or 1, we can interpret the traversal path naturally as a binary sequence. The expected output is a single integer representing the total sum of all binary values generated by root-to-leaf paths.

The constraints tell us several important things:

  • The tree contains between 1 and 1000 nodes.
  • Each node value is guaranteed to be either 0 or 1.
  • The final answer fits inside a 32-bit integer.

Since the tree size is relatively small, an O(n) solution is more than sufficient. The binary value of a path can be updated incrementally during traversal instead of reconstructing binary strings repeatedly.

Several edge cases are worth identifying upfront. A tree with only one node means the root itself is also a leaf, so its value alone forms the result. Trees that are heavily skewed, meaning every node only has one child, effectively behave like linked lists and test recursion depth behavior. Another important case is when all node values are 0, since every root-to-leaf binary number becomes zero.

Approaches

Brute Force Approach

A straightforward approach is to explicitly construct every root-to-leaf binary number as a string.

We can perform a depth-first traversal and maintain a string representing the current path. At each node, append the node's value ("0" or "1"). When reaching a leaf node, convert the accumulated binary string into an integer using base-2 conversion and add it to the result.

This approach is correct because every root-to-leaf path is visited exactly once, and each generated binary string corresponds precisely to the intended binary number.

However, this method is inefficient because string concatenation and repeated binary conversions add overhead. Every leaf requires parsing a binary string, and intermediate string creation increases memory usage unnecessarily.

Optimal Approach

The key observation is that we do not need to store the binary path as a string. Instead, we can build the number incrementally while traversing the tree.

Binary numbers follow a useful property:

If the current binary number is x, appending a new bit b produces:

new_value = (x << 1) | b

Shifting left by one bit multiplies the current number by 2, making room for the next bit. Then we insert the new node value using bitwise OR.

For example:

Current number: 101 (decimal 5)

Appending 1:

101 -> 1011

Mathematically:

(5 << 1) | 1 = 10 | 1 = 11

Using this observation, we can perform a DFS traversal while maintaining the current accumulated binary number. Once we reach a leaf, we simply add the computed value to the final sum.

This avoids string construction entirely and processes each node exactly once.

Approach Time Complexity Space Complexity Notes
Brute Force O(n × h) O(h) Builds binary strings and converts them at leaves
Optimal O(n) O(h) DFS with incremental binary computation

Here, n is the number of nodes and h is the height of the tree.

Algorithm Walkthrough

Optimal DFS Algorithm

  1. Start a depth-first traversal from the root node and initialize the current binary value as 0.
  2. At each node, update the current number using:

current = (current << 1) | node.val

This shifts the accumulated bits left and appends the current node's value. 3. Check whether the node is a leaf node. A node is a leaf if both left and right are None. 4. If the node is a leaf, add the computed binary value to the running total because this represents one complete root-to-leaf number. 5. Otherwise, recursively continue traversal into the left and right subtrees while passing the updated binary value. 6. Return the total sum after traversal completes.

Why it works

The algorithm maintains an invariant: at every node, current represents the decimal value of the binary number formed by the path from the root to that node.

Since binary numbers are constructed by shifting left and appending bits, every recursive call correctly updates the path value. Because DFS visits every root-to-leaf path exactly once and only leaf nodes contribute to the sum, the final result is guaranteed to be correct.

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

from typing import Optional

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node: Optional[TreeNode], current_value: int) -> int:
            if not node:
                return 0

            current_value = (current_value << 1) | node.val

            if not node.left and not node.right:
                return current_value

            left_sum = dfs(node.left, current_value)
            right_sum = dfs(node.right, current_value)

            return left_sum + right_sum

        return dfs(root, 0)

The implementation uses a helper DFS function that accepts two parameters: the current node and the accumulated binary value so far.

The base case handles None nodes by returning 0, which simplifies recursive summation.

At every node, we update the binary number using:

current_value = (current_value << 1) | node.val

This efficiently appends the node's binary digit.

If we reach a leaf node, we return the computed value immediately because that path is complete. Otherwise, we recursively compute the contribution from the left and right subtrees and sum their results.

Finally, the main function starts DFS from the root with an initial value of 0.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) int {
	var dfs func(node *TreeNode, currentValue int) int

	dfs = func(node *TreeNode, currentValue int) int {
		if node == nil {
			return 0
		}

		currentValue = (currentValue << 1) | node.Val

		if node.Left == nil && node.Right == nil {
			return currentValue
		}

		leftSum := dfs(node.Left, currentValue)
		rightSum := dfs(node.Right, currentValue)

		return leftSum + rightSum
	}

	return dfs(root, 0)
}

The Go implementation follows the exact same logic as the Python solution.

Instead of nested functions being automatically supported like Python, we explicitly declare a recursive function variable:

var dfs func(node *TreeNode, currentValue int) int

Go uses nil instead of None for missing nodes. Leaf detection is similarly handled by checking whether both children are nil.

Since the problem guarantees that the result fits inside a 32-bit integer, standard Go int arithmetic is sufficient.

Worked Examples

Example 1

Input

root = [1,0,1,0,1,0,1]

Tree structure:

        1
      /   \
     0     1
    / \   / \
   0   1 0   1

The traversal evolves as follows:

Node Previous Value Updated Value Binary Representation Leaf? Running Sum
1 0 1 1 No 0
0 1 2 10 No 0
0 2 4 100 Yes 4
1 2 5 101 Yes 9
1 1 3 11 No 9
0 3 6 110 Yes 15
1 3 7 111 Yes 22

Final result:

4 + 5 + 6 + 7 = 22

Example 2

Input

root = [0]

Tree structure:

0

Traversal:

Node Previous Value Updated Value Leaf? Running Sum
0 0 0 Yes 0

Final result:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack stores at most tree height

The algorithm performs a single DFS traversal through the tree, meaning each node contributes a constant amount of work. Therefore, the runtime is linear in the number of nodes.

The auxiliary space comes from recursion depth. In the worst case of a skewed tree, the height becomes n, producing O(n) stack usage. In a balanced tree, the height is approximately log n.

Test Cases

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

solution = Solution()

# Example 1
root1 = TreeNode(
    1,
    TreeNode(0, TreeNode(0), TreeNode(1)),
    TreeNode(1, TreeNode(0), TreeNode(1))
)
assert solution.sumRootToLeaf(root1) == 22  # standard balanced tree example

# Example 2
root2 = TreeNode(0)
assert solution.sumRootToLeaf(root2) == 0  # single-node zero tree

# Single node with value 1
root3 = TreeNode(1)
assert solution.sumRootToLeaf(root3) == 1  # root itself forms binary 1

# Left-skewed tree
root4 = TreeNode(
    1,
    TreeNode(
        0,
        TreeNode(1)
    )
)
assert solution.sumRootToLeaf(root4) == 5  # binary 101 = 5

# Right-skewed tree
root5 = TreeNode(
    1,
    None,
    TreeNode(
        1,
        None,
        TreeNode(0)
    )
)
assert solution.sumRootToLeaf(root5) == 6  # binary 110 = 6

# All zeros tree
root6 = TreeNode(
    0,
    TreeNode(0),
    TreeNode(0)
)
assert solution.sumRootToLeaf(root6) == 0  # all paths evaluate to zero

# Mixed values tree
root7 = TreeNode(
    1,
    TreeNode(1),
    TreeNode(0)
)
assert solution.sumRootToLeaf(root7) == 5  # 11 + 10 = 3 + 2

print("All test cases passed!")
Test Why
[1,0,1,0,1,0,1] Validates standard balanced tree traversal
[0] Tests smallest possible input
[1] Ensures single-node nonzero value works
Left-skewed tree Validates recursion through one branch
Right-skewed tree Ensures missing left children are handled
All zeros tree Confirms binary accumulation handles zeros correctly
Mixed values tree Verifies multiple root-to-leaf sums

Edge Cases

Single Node Tree

A tree containing only one node is an important edge case because the root is also a leaf. A buggy implementation might incorrectly assume traversal must continue deeper. Our solution correctly identifies that both child pointers are absent and immediately returns the root value.

For example:

1

This produces the binary number 1, resulting in output 1.

Skewed Tree

A tree where every node has only one child behaves like a linked list. This can expose bugs in recursive traversal logic if child existence is not checked carefully.

Example:

1
 \
  0
   \
    1

This represents binary 101, which equals 5. Since our DFS recursively handles missing children by returning 0, skewed trees work naturally.

All Zero Values

If every node contains 0, every root-to-leaf path evaluates to binary zero. A naive implementation that mishandles leading zeros or string conversion could produce incorrect values.

Example:

    0
   / \
  0   0

Each path evaluates to 0, so the total sum remains 0. Since our implementation computes values numerically through bit shifts, leading zeros are handled automatically and correctly.

Deep Tree With Many Leaves

A tree containing many leaf nodes tests whether all paths are accumulated correctly. Some incorrect solutions overwrite results instead of summing them.

Because this implementation returns subtree sums recursively and combines them with:

left_sum + right_sum

every leaf contribution is preserved exactly once.