Micro-questions over the level-order traversal module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.

Reference tree:

        1
      /   \
     2     3
    / \
   4   5

A. The idea

1. What is level-order traversal?

Answer

Visiting nodes level by level, top to bottom and left to right within each level.

2. What is its other name?

Answer

Breadth-first traversal — BFS applied to a tree.

3. Level-order output on the reference tree?

Answer

[1, 2, 3, 4, 5]

4. Why can level-order not be written recursively (in the natural way)?

Answer

Recursion uses the call stack, which is LIFO. Level-order needs FIFO — you must finish the nodes you met earliest first, and a stack gives you the latest.

5. What data structure does it use instead?

Answer

An explicit queue — collections.deque in Python, with popleft().


B. The mechanism

6. Describe the loop.

Answer

Start with the root in the queue. While the queue is non-empty: popleft() a node, visit it, and enqueue its left child then its right child if they exist.

7. Why enqueue left before right?

Answer

A queue returns things in the order they went in, so enqueuing left first makes left come out first — giving left-to-right order within each level.

8. How do you produce output grouped by level rather than a flat list?

Answer

At the top of each iteration, record len(queue) — that is exactly the number of nodes on the current level. Process that many, collecting them into one sublist, before starting the next.

9. Why does len(queue) at the start of an iteration equal the level width?

Answer

Because at that moment the queue holds every node of the current level and nothing else — all of the previous level has been popped, and none of the next level has been enqueued except by nodes you are about to process.


C. Costs

10. Time complexity?

Answer

— every node is enqueued once and dequeued once.

11. Space complexity, and in terms of what?

Answer

where is the maximum width of the tree — the widest level, not the height.

12. What is for a perfect binary tree?

Answer

About — the bottom level holds half of all nodes. So BFS can use far more memory than DFS on the same tree.

13. Compare DFS and BFS space on a balanced tree, and on a degenerate one.

Answer

Balanced: DFS , BFS — DFS wins.
Degenerate: DFS , BFS (one node per level) — BFS wins.
They are worst on opposite shapes.


D. Choosing between them

14. When is level-order the right choice?

Answer

When the answer depends on depth — finding the shallowest node satisfying something, shortest path in an unweighted graph, printing a tree level by level.

15. When is depth-first the right choice?

Answer

When the answer depends on a whole root-to-leaf path or on combining results from subtrees, and when memory on a wide tree matters.

16. Why does BFS find the shallowest match and DFS does not?

Answer

BFS exhausts depth entirely before touching depth , so the first match it finds is guaranteed minimal-depth. DFS may plunge down a deep branch and find a much deeper match first.


E. Traps

17. What happens on a deep tree with recursive DFS?

Answer

Stack overflow — a RecursionError in Python at a height around 10,000. Use an explicit iterative stack for deep trees.

18. What happens if you use pop() instead of popleft() in BFS?

Answer

The queue becomes a stack and BFS silently turns into a bizarre right-to-left DFS. It still runs and still visits every node, which is what makes the bug hard to spot.

19. What is the in-order fallacy?

Answer

Assuming in-order gives sorted output on any binary tree. It only does so on a binary search tree; on an arbitrary binary tree it guarantees nothing.

20. Summarise level-order in one sentence.

Answer

The same traversal with a queue instead of a stack — which trades memory for and buys the guarantee that shallower nodes come first.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Traversal