How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Traverse levels selecting nodes meeting a predicate

Quick Overview

Traverse levels selecting nodes meeting a predicate evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given the root of a binary tree and a predicate P(value) that returns true for certain node values, return a list of lists where the i-th list contains the values at depth i that satisfy P. Implement an iterative traversal that uses a stack to manage nodes per level (no recursion). Clearly explain how you detect level boundaries, maintain per-level collections, and analyze time and space complexity.

Quick Answer: Traverse levels selecting nodes meeting a predicate evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Given a binary tree and a predicate, return the values at each depth that satisfy the predicate, level by level. The tree is given as a **level-order list** `tree` (LeetCode style), where `null`/`None` marks a missing child. The predicate `P(value)` is concretized here as `value % k == 0` for a given positive integer `k`. Return a list of lists where the i-th list contains the values at depth `i` (left-to-right) that satisfy the predicate. **A depth with no satisfying values still contributes an empty list** for that level, so the number of returned lists equals the height of the tree. Implement an **iterative** traversal (no recursion). Use an explicit frontier/stack of the current level's nodes; detect level boundaries by processing one full level at a time and building the next level's frontier as you go. **Example** ``` tree = [1, 2, 3, 4, 5, 6, 7], k = 2 1 / \ 2 3 / \ / \ 4 5 6 7 Depth 0: [1] -> even: [] Depth 1: [2, 3] -> even: [2] Depth 2: [4,5,6,7] -> even: [4, 6] Result: [[], [2], [4, 6]] ``` If the tree is empty, return `[]`.

Constraints

0 <= number of nodes <= 10^4
Node values fit in a 32-bit signed integer (may be negative or zero).
1 <= k (the predicate divisor); P(v) is true iff v % k == 0.
tree is a level-order encoding; None/null marks a missing child.
A depth with zero satisfying values still yields an empty list, so len(result) equals the tree height.
Must be iterative — no recursion.

Examples

Input: ([1, 2, 3, 4, 5, 6, 7], 2)

Expected Output: [[], [2], [4, 6]]

Explanation: Full 3-level tree. Depth 0 has only 1 (odd) -> []. Depth 1 has 2,3 -> even: [2]. Depth 2 has 4,5,6,7 -> even: [4, 6].

Input: ([2, 4, 6, 8, 10, 12, 14], 2)

Expected Output: [[2], [4, 6], [8, 10, 12, 14]]

Explanation: Every value is even, so each level's full set of values is kept.

Input: ([1, 3, 5, 7, 9], 2)

Expected Output: [[], [], []]

Explanation: Tree is 1 -> (3,5); 3 -> (7,9), giving 3 levels. No even values anywhere, so three empty lists — one per depth.

Input: ([10], 5)

Expected Output: [[10]]

Explanation: Single-node tree; 10 % 5 == 0, so the root value is kept at depth 0.

Input: ([], 3)

Expected Output: []

Explanation: Empty tree returns an empty list of levels.

Input: ([6, None, 9, None, 12], 3)

Expected Output: [[6], [9], [12]]

Explanation: None gaps create a right-leaning chain 6 -> 9 -> 12. Each value is divisible by 3, one per depth.

Input: ([-4, -2, -1, 0, 3], 2)

Expected Output: [[-4], [-2], [0]]

Explanation: Tree is -4 -> (-2,-1); -2 -> (0,3). Even values by depth: [-4], then [-2] (-1 is odd), then [0] (3 is odd). Confirms negatives and zero are handled.

Input: ([15, 30, 7, 45, 22, 9, 60], 15)

Expected Output: [[15], [30], [45, 60]]

Explanation: Divisor 15. Depth 0: 15. Depth 1: 30 (7 not divisible). Depth 2: 45 and 60 (22 and 9 not divisible).

Hints

Reconstruct the tree from the level-order list, or process the list directly — either way you need to know each node's depth.
Process exactly one level at a time: hold the current level's nodes in a list (the frontier), and while scanning it, build the next level's frontier from the children.
The level boundary is implicit: when you finish draining the current frontier, you have collected all satisfying values for that depth and assembled the complete next frontier.
Append an empty list for a level even when no node there satisfies the predicate, so the i-th list always corresponds to depth i.

Quick Overview