Katkat
Back

Sum the Binary Numbers Spelled by Root-to-Leaf Paths in a 0/1 Tree

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

Given a binary tree of 0 and 1 bits in level-order form, return the sum of the binary numbers spelled by every root-to-leaf path, reading the root as the most significant bit. The problem tests tree traversal, carrying an accumulated value down each path, and parsing a level-order serialization correctly.

You are given a binary tree in which every node holds the bit 0 or 1. Each path from the root down to a leaf spells a binary number, read with the root as the most significant bit: for example, the path 1 -> 0 -> 1 spells binary 101, which is 5. Return the sum of the numbers spelled by all root-to-leaf paths.

Function Signature

def sum_root_to_leaf_numbers(root: list[int | None]) -> int:

root is the tree in level-order form, as described under Rules.

Rules

  • Level-order form: root[0] is the root's value. The remaining entries are read in pairs, one pair for each non-None node in the order the nodes appear in the list. The first entry of a pair is that node's left child and the second is its right child; None means the child is absent. Trailing None entries may be omitted, and a node whose pair lies beyond the end of the list has no children.
  • A leaf is a node with no children. Every leaf contributes exactly one path.
  • Leading zeros are allowed: the path 0 -> 1 -> 1 spells binary 011, which is 3.
  • If the root has no children, the tree has a single path, and the answer is the root's bit.

Constraints

  • The tree has between 1 and 1,000 nodes, 1 <= len(root) <= 2001, and root[0] is not None.
  • Every entry other than None is 0 or 1.
  • Every root-to-leaf path has at most 31 nodes, so each path's number is at most 2^31 - 1.
  • The tests guarantee that the answer is at most 2^31 - 1.

Examples

Example 1

Input: root = [1, 1, 0, None, 1, 1]
Output: 12

The root 1 has left child 1 and right child 0. The left child has no left child and a right child 1. The right child has a left child 1, and its right child is omitted. The paths are 1 -> 1 -> 1 (binary 111, which is 7) and 1 -> 0 -> 1 (binary 101, which is 5), so the sum is 12.

Example 2

Input: root = [1, 0, None, 0, 1]
Output: 9

The root has only a left child 0, whose children are 0 and 1. The paths spell 100 (4) and 101 (5).

Example 3

Input: root = [0]
Output: 0

The root is a leaf, and its single path spells 0.