Traverse levels selecting nodes meeting a predicate

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Traverse Levels Selecting Nodes Meeting a Predicate

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.

Hints

1. Reconstruct the tree from the level-order list, or process the list directly — either way you need to know each node's depth.
2. 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.
3. 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.
4. 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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Choose traversal based on the required view or aggregate. DFS is natural for subtree computations and reconstruction; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.