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.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.
C++
Java
Python
C#
JavaScript
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.
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.
| 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. |
Sum Root to Leaf Numbers - Coding Interview Question - Leetcode 129 • NeetCode • 36,478 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