Quick Overview

Sum all numbers formed by root-to-leaf digit paths in a binary tree represented as a heap array. Carry each decimal prefix through the traversal, add only at leaves, and analyze recursive versus iterative space.

Sum Numbers Formed by Root-to-Leaf Paths

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Implement `sum_root_to_leaf_numbers(values)` for a binary tree serialized as a zero-based heap array. For an existing node at index `i`, its children are at `2 * i + 1` and `2 * i + 2`. A `null` slot means no node, and an existing node never appears below a missing parent. Every existing value is a decimal digit from `0` through `9`. Each root-to-leaf path forms a number by concatenating its digits from root to leaf. Return the sum of all such numbers. A leaf has no existing left or right child, and an empty serialization returns `0`. For example, a root `1` with children `2` and `3` forms `12` and `13`, so the result is `25`. ```hint Carry the prefix numerically When visiting digit `d` with accumulated prefix `p`, the new prefix is `p * 10 + d`. ``` ```hint Add only at leaves Internal prefixes are not complete path numbers. Contribute the accumulated value only when both children are absent. ``` ### Discussion Extensions - How would an iterative depth-first traversal avoid recursion depth limits on a very deep tree? - What is the time complexity in terms of nodes and the auxiliary space in terms of tree height?

Quick Answer: Sum all numbers formed by root-to-leaf digit paths in a binary tree represented as a heap array. Carry each decimal prefix through the traversal, add only at leaves, and analyze recursive versus iterative space.

Implement sum_root_to_leaf_numbers(values) for a binary tree serialized as a zero-based heap array with null slots and decimal-digit node values. Concatenate digits along every root-to-leaf path and return the sum of the resulting numbers; return zero for an empty tree.

Constraints

  • 0 <= values.length <= 255, and an existing node never appears below a null parent.
  • Each existing node value is a decimal digit from 0 through 9.
  • The final sum fits in a signed 64-bit integer.

Examples

Input: ([1, 2, 3],)

Expected Output: 25

Input: ([4, 9, 0, 5, 1],)

Expected Output: 1026

Hints

  1. Carry a numeric prefix and update it as prefix * 10 + digit when visiting a node.
  2. Add a prefix only when neither serialized child index contains an existing node.

Loading coding console...