Sum of Root To Leaf Binary Numbers

Binary TreeDepth-First SearchRecursionTree

Given a binary tree where each node can either be 0 or 1, compute the sum of the values of all paths from the root to the leaves, where each path's value is interpreted as a binary number.

Example 1

Input

[
  1,
  0,
  1,
  0,
  1,
  0,
  1
]

Output

Explanation. The tree can be visualized as: 1 / \ 0 1 / \ / \ 0 1 0 1 The binary numbers from root to leaves are: 100 (4), 101 (5), 110 (6), 111 (7). Sum = 4 + 5 + 6 + 7 = 22.

Example 2

Input

[
  0
]

Output

Explanation. The tree only has one node, which is root and also a leaf with value 0. The binary number is 0.

Example 3

Input

[
  1,
  1,
  1,
  1,
  1,
  1,
  1
]

Output

Explanation. The tree can be visualized as: 1 / \ 1 1 / \ / \ 1 1 1 1 All paths are: 1111, 1111, 1111, 1111. Each converted to decimal is 15. Sum = 15 + 15 = 30.

Follow-up: How can the solution be optimized for a balanced binary tree? Discuss if caching can assist in improving the computational complexity.

Constraints:

The given tree will have between 1 and 1000 nodes. Each node's value is either 0 or 1.

Views: 2