Solve tree leaf sum and target indices search
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
LeetCode 129. Sum Root to Leaf Numbers LeetCode 2089. Find Target Indices After Sorting Array (array already sorted; require O(log n) time)
https://leetcode.com/problems/sum-root-to-leaf-numbers/description/ https://leetcode.com/problems/find-target-indices-after-sorting-array/description/
Quick Answer: This question evaluates proficiency in tree traversal and array search algorithms, specifically handling recursive depth-first traversal with path-based numeric accumulation and performing logarithmic-time search over sorted data.
Given (1) a binary tree represented as a level-order array where tree[i] is either a digit 0-9 or None, and (2) a non-decreasing sorted array nums with an integer target, implement a function that returns a tuple (sum_root_to_leaf, target_indices). For the tree, interpret each root-to-leaf path as a number formed by concatenating node digits (e.g., path 1->2->3 forms 123) and return the sum of all such numbers. For the array, return a list of all indices i such that nums[i] == target. Use O(n) for the tree traversal and O(log m + k) for the index search (m = len(nums), k = number of matches).
Constraints
- 0 <= len(tree) <= 200000
- tree is a level-order (array) representation; children of index i are at 2*i+1 and 2*i+2 when within bounds
- Each non-None tree value is an integer digit in [0, 9]
- 0 <= len(nums) <= 200000
- nums is sorted in non-decreasing order
- Return indices in ascending order
- Sum of root-to-leaf numbers fits in 64-bit signed integer
- Time: O(n) for tree processing, O(log m + k) for index search; Space: O(h + k), where h is tree height and k is number of matches
Solution
from typing import List, Optional, Tuple
import bisect
def tree_leaf_sum_and_target_indices(tree: List[Optional[int]], nums: List[int], target: int) -> Tuple[int, List[int]]:
# Part 1: Sum of root-to-leaf numbers from level-order array representation
total = 0
n = len(tree)
def valid(idx: int) -> bool:
return 0 <= idx < n and tree[idx] is not None
if n > 0 and tree[0] is not None:
stack: List[Tuple[int, int]] = [(0, 0)] # (index in tree, number so far)
while stack:
idx, cur = stack.pop()
if not valid(idx):
continue
val = int(tree[idx]) # digits 0-9
new_num = cur * 10 + val
left = 2 * idx + 1
right = 2 * idx + 2
is_left_valid = valid(left)
is_right_valid = valid(right)
if not is_left_valid and not is_right_valid:
total += new_num
else:
if is_left_valid:
stack.append((left, new_num))
if is_right_valid:
stack.append((right, new_num))
# Part 2: Indices of target in a sorted array using binary search
l = bisect.bisect_left(nums, target)
r = bisect.bisect_right(nums, target)
indices = list(range(l, r)) if l < r else []
return total, indices
Explanation
The tree is processed iteratively using a stack over the array-based representation. For each valid node index i, we propagate the accumulated number new_num = prev*10 + tree[i]. A node is a leaf if both children are either out of bounds or None; at leaves we add new_num to the total. This traversal runs in O(n). For the array task, binary searches (lower and upper bounds) find the contiguous block of target values in O(log m), and enumerating the indices costs O(k).
Time complexity: O(n + log m + k). Space complexity: O(h + k).
Hints
- Treat the tree list as a heap-like level-order; skip None nodes.
- Use DFS or BFS carrying the numeric value so far: new_val = prev*10 + node_val.
- A node is a leaf if both children are out of bounds or None.
- Use binary search (bisect_left and bisect_right) to find the range of target indices in O(log n).