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.In #1022 Sum of Root To Leaf Binary Numbers, each root‑to‑leaf path in a binary tree represents a binary number formed by the node values (0 or 1). The key idea is to traverse the tree and progressively build the binary value for the current path.
A common approach is using Depth‑First Search (DFS). As you move from the root to a child node, update the current number by shifting the existing value left (current * 2) and adding the node’s value. This simulates constructing a binary number digit by digit. When a leaf node is reached, the constructed number represents one valid root‑to‑leaf binary value and should be added to the total sum.
The traversal continues until all paths are processed. DFS can be implemented using recursion or an explicit stack. Since every node is visited once, the algorithm is efficient for typical binary tree sizes.
Time complexity is linear relative to the number of nodes, while space complexity depends on the height of the tree due to recursion or stack usage.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Depth-First Search (Recursive) | O(n) | O(h) |
| Depth-First Search (Iterative Stack) | O(n) | O(h) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Find each path, then transform that path to an integer in base 10.
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).
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).
1#include <stdio.h>
2#include <stdlib.h>
3
4struct TreeNode {
5 int val;
6 struct TreeNode
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.
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.
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.
1function TreeNode(val, left, right
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
DFS is preferred because the problem focuses on root-to-leaf paths. DFS naturally processes one path at a time, making it easy to maintain the current binary value without storing multiple partial paths simultaneously.
Yes, variations of this problem appear in technical interviews at companies like Google, Amazon, and Meta. It tests understanding of tree traversal, recursion, and how to efficiently propagate state along a path in a tree.
A binary tree traversal structure using recursion or a stack works best. DFS is particularly suitable because it naturally follows root-to-leaf paths, allowing the binary value to be built incrementally along each path.
The optimal approach uses Depth-First Search (DFS) to traverse the binary tree while building the binary number along the path. At each node, shift the current value left and add the node’s bit. When a leaf node is reached, add the constructed value to the total sum.
This JavaScript solution uses a stack to carry out an iterative DFS, forming binary numbers for root-to-leaf paths and calculating their sum without recursion. Each stack entry comprises a node and its ongoing binary sum, unraveling all paths systematically.