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.
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-bits integer.
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:
[1, 1000].Node.val is 0 or 1.Problem Overview: Each root-to-leaf path in the binary tree represents a binary number where every node contributes a bit (0 or 1). Moving from the root to a leaf builds a binary sequence. Convert each path into its decimal value and return the sum of all such numbers.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(n), Space: O(h))
This approach traverses the tree using recursion. As you move down a path, maintain the current binary value formed so far. At each node, shift the accumulated value left by one bit (current << 1) and add the node’s value using a bitwise OR or addition. When a leaf node is reached, the accumulated value represents a full binary number, so add it to the total sum.
The key insight: binary digits are built incrementally as you traverse the path. Shifting left is equivalent to multiplying by 2, which matches how binary numbers grow when a new bit is appended. Every node is processed exactly once, making the time complexity O(n) where n is the number of nodes. Recursion depth depends on the tree height, so space complexity is O(h). This method naturally fits problems involving path-based computations in tree structures and is the cleanest implementation using Depth-First Search.
Approach 2: Iterative Depth-First Search with Stack (Time: O(n), Space: O(h))
The iterative version replaces recursion with an explicit stack. Each stack entry stores a pair: the current node and the binary value built along the path to that node. Pop a node from the stack, update the binary value using the same shift operation (value = (value << 1) | node.val), and check whether it is a leaf. If it is, add the value to the total sum. Otherwise, push its children onto the stack with the updated value.
This approach performs the same logical steps as recursive DFS but avoids relying on the call stack. It is useful in environments where recursion depth might be limited or when you want explicit control over traversal order. Time complexity remains O(n) since each node is visited once, and the stack holds at most O(h) nodes at a time in a balanced binary tree.
Recommended for interviews: Recursive DFS is typically expected because the code is concise and directly mirrors the tree structure. Interviewers look for the insight that the path forms a binary number and can be built incrementally using a left shift operation. Implementing the iterative stack version demonstrates deeper understanding of DFS mechanics and control over recursion.
This approach involves using a recursive function to traverse the binary tree from the root to the leaves. During the traversal, we calculate the binary number formed by the path from the root to the current node, then sum up the numbers obtained when a leaf node is reached. The traversal is achieved using depth-first search (DFS).
This C solution defines a `TreeNode` structure for binary trees. The function `calculateSum` is recursive and is responsible for traversing the tree. It uses a `currentSum` variable that is left-shifted to build the binary number. When a leaf node is reached, it returns the binary-to-decimal converted number. Otherwise, it continues the DFS traversal.
Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack. In the worst case, it could be O(n).
This approach utilizes an iterative technique employing a stack to carry out a DFS. In each iteration, nodes are retrieved alongside their corresponding computed binary sum. This method is advantageous when stack overflow due to recursion is a concern, as it emulates recursion iteratively.
In this Java solution, a stack is employed to simulate the recursion process iteratively. Each `Pair` in the stack holds a tree node and the current binary sum. The stack facilitates traversing the tree and computing the sum without needing traditional recursion.
Java
Python
JavaScript
Time Complexity: O(n), due to visiting each node once.
Space Complexity: O(n), bounded by the stack's requirement to store node-state pairs.
We design a recursive function dfs(root, t), which takes two parameters: the current node root and the binary number t corresponding to the parent node of the current node. The return value of the function is the sum of binary numbers represented by paths from the current node to leaf nodes. The answer is \textrm{dfs}(root, 0).
The logic of the recursive function is as follows:
root is null, return 0; otherwise, calculate the binary number t corresponding to the current node, i.e., t = t \ll 1 | root.val.t; otherwise, return the sum of \textrm{dfs}(root.left, t) and \textrm{dfs}(root.right, t).The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the binary tree. Each node is visited once; the recursion stack requires O(n) space.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) | Time Complexity: O(n), where n is the number of nodes in the tree because each node is visited once. |
| Iterative Depth-First Search (DFS) with Stack | Time Complexity: O(n), due to visiting each node once. |
| Recursion | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Depth-First Search (DFS) | O(n) | O(h) | Best general solution. Clean and intuitive for tree traversal problems. |
| Iterative DFS with Stack | O(n) | O(h) | Useful when avoiding recursion or when stack-based traversal control is preferred. |
Sum of Root To Leaf Binary Numbers | LeetCode 1022 | C++, Java, Python • Knowledge Center • 9,179 views views
Watch 9 more video solutions →Practice Sum of Root To Leaf Binary Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor