Sum of Root to Leaf Binary Numbers
Given a binary tree each node holding a binary digit (0 or 1), consider the number represented by the path from the root to any leaf by appending the binary digits from top to bottom. Your task is to calculate the sum of all numbers obtained in such a way from root to all leaves.
For example, given the binary tree below:
1
/ \
0 1
/ \ / \
0 1 0 1
The numbers formed by root-to-leaf paths are:
- 100 (4 in decimal)
- 101 (5 in decimal)
- 110 (6 in decimal)
- 111 (7 in decimal)
The sum of these numbers: 4 + 5 + 6 + 7 = 22.
[ [ 1, 0, 1, 0, 1, 0, 1 ] ]
Explanation. Each number represents a level in the binary tree. Root node is 1, followed by two children nodes 0 and 1, and so on. The numbers formed by root-to-leaf paths are 100 (4 in decimal), 101 (5 in decimal), 110 (6 in decimal), and 111 (7 in decimal). Sum is 22.
[ [ 0 ] ]
Explanation. The root and the only node is 0, which corresponds to 0 in decimal.
[ [ 1, 1, 1 ] ]
Explanation. The binary tree has only three nodes, forming one path: 11 (3 in decimal). Since there's only this path, the sum is just 3.
Follow-up: As a follow-up, consider implementing your solution recursively and iteratively. What are the trade-offs (in terms of complexity and readability) between these two approaches?
The tree will have at least one node and at most 1000 nodes. Each node in the tree only contains the value 0 or 1.
- Views
- 9