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
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Level-Order Traversal — the module
- Depth-First Traversals — Question Bank — the other three orders
- Breadth-First Search — the same idea on a general graph
Software engineering
Infrastructure & security
Computer science
Hardware & engineering