What space does BFS use?
Practice this question from Binary Tree Level Order Traversal - BFS queue Pattern Practice Quiz, with options and an explanation.
Question
What space does BFS use?
Option A — Correct answer
O(w), where w is maximum tree width
Option B
O(1) always
Option C
O(n^2)
Option D
O(log log n)
Explanation
The queue can hold up to the maximum width of the tree.