Quick Overview

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.

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/

Overview: 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

  1. Treat the tree list as a heap-like level-order; skip None nodes.
  2. Use DFS or BFS carrying the numeric value so far: new_val = prev*10 + node_val.
  3. A node is a leaf if both children are out of bounds or None.
  4. Use binary search (bisect_left and bisect_right) to find the range of target indices in O(log n).

Loading coding console...

Show the approach

Approach

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)