Question bank — Level-order traversal — BFS with queue

False — a Stack (LIFO) serves the newest node first, diving deep down one path; only a queue's first-in-first-out order keeps the oldest (closest-to-root) node processed first, which is what level order needs.

True — a tree has exactly one path from root to any node, so the number of edges you walk (distance) equals the depth; that is why Breadth-First Search (BFS), which expands by increasing distance, gives level order here.

False — BFS holds ~one level (width $w$), DFS holds ~one path (height $h$). On a tall skinny tree DFS is worse; on a wide bushy tree BFS is worse. Neither dominates.

True for order, false for speed — you still get correct level order, but each pop(0) shifts every element ($O(n)$), turning the whole traversal into $O(n^2)$.

False — during a round the queue briefly holds the tail of the current level plus already-enqueued children of the next level, so it can hold up to roughly two partial levels; the snapshot trick is what keeps the grouping clean despite this.

False — the root is enqueued first and therefore dequeued and visited first; "front of the queue" is the oldest item, and the root is the oldest.

False — they visit nodes in the same order; grouping only adds "fences" (via the size snapshot) to split that one stream into per-level sublists.

False — space is $O(w)$, and the widest level (the bottom) of a complete tree holds $\approx n/2$ nodes, so it is $O(n)$; $O(\log n)$ is the height, which governs DFS, not BFS.

It enqueues None for missing children, so a later dequeue does None.left and crashes; guard with if node.left / if node.right before enqueuing.

The length grows as children are enqueued mid-loop, so the loop keeps running past the current level and bleeds nodes from the next floor into this group; snapshot n = len(queue) once before the loop.

pop() from the back is LIFO — they get a depth-first (pre-order-ish) walk down the rightmost-added path, not level order; see Depth-First Search (DFS).

Enqueuing a None root means the queue is not empty, so the loop runs and dereferences None; check if root is None: return [] before enqueuing anything.

For the flat node-visit order it makes no difference to which nodes appear when, since children of level $k$ are still processed only after all of level $k$; but mixing visit/enqueue order can matter if you also read queue state — keep visit → enqueue for clarity.

Within each level the output flips to right-to-left; the level grouping stays correct but the required left-to-right order is broken.

When all of level $k$ is enqueued, none of level $k+1$ has been enqueued yet; since we always dequeue the oldest, every level-$k$ node (and its child-enqueues) is handled before any level-$(k+1)$ node is reached.

At any instant the queue holds only the frontier — roughly one level — so it grows with the widest level $w$; it only equals $O(n)$ when the widest level itself is $\approx n$.

Because it expands nodes strictly by increasing distance, the first time it reaches a node is via a fewest-edge path — see Shortest path in unweighted graphs.

Right before a round begins, the queue contains precisely the nodes discovered on the previous round — i.e. the whole current level and nothing else — so its length is that level's node count.

Each node is enqueued exactly once and dequeued exactly once, and processing it (visit + push up to two children) is constant work, so total work scales linearly with node count.

The container's ordering is the algorithm: LIFO postpones siblings and dives deep (DFS), FIFO postpones depth and sweeps wide (BFS). Swapping the container swaps the traversal.

An empty list [] — the guard if root is None returns before enqueuing, so the loop never runs.

Max queue size is 1 (just the root), so space is $O(1)$; there is one level with one node.

$O(1)$ — the queue never holds more than one node at a time because each level has exactly one node; here width $=1$ even though height $=n$.

When the entire deepest (fullest) level is queued — about $n/2$ nodes — giving the $O(n)$ worst-case space; this is the Tree height vs width trade-off at its extreme.

No — traversal depends only on structure (parent/child links), not on values; the visit order and complexity are unchanged.

It enqueues the left child and skips the right (if node.right is false), so no None enters the queue and the level width simply reflects the one real child.