Tree traversal, BFS

Breadth-first traversal visits a tree level by level. Put the root in a queue, then while the queue is nonempty, either pop one node for a flat order or snapshot levelSize=queue.size() and pop exactly that many nodes to build one level. Enqueue left then right children so the usual left-to-right order is deterministic. The level-size snapshot is important: children added during this pass belong to the next level, not the current one. Every node is enqueued and dequeued once, so time is O(n) and queue space is O(w), where w is maximum width; in the worst case this is O(n). Check null root, one node, a skewed tree, and a complete last level. If the input may contain cycles, keep a visited set because it is no longer a tree.