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
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).