Traverse binary tree by levels with constraints

Q: Traverse binary tree by levels with constraints

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Traverse binary tree by levels with constraints

Overview

Comments (0)