Traverse binary tree by levels with constraints
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a binary tree and a predicate P(node), perform a level-by-level traversal that collects, for each level, only the nodes whose values satisfy P. Implement this traversal using stacks only (no queues), returning a list of levels with nodes in left-to-right order within each level. Explain the algorithm, its correctness, and analyze the time and space complexities. As a follow-up, adapt your method to output zigzag order while still using only stacks.
Overview: This question evaluates binary tree traversal techniques, use of stacks as constrained data structures, predicate-based filtering of nodes, and the ability to argue algorithmic correctness and analyze time and space complexity.