Question

Which data structure is used for level order traversal in trees?

• A. Stack
• B. Queue
• C. Array
• D. Tree

Hint:

Remember: Depth-First traversals (Pre/In/Post) use a Stack (implicitly via recursion), while Breadth-First traversals (Level Order) always use a Queue.

Answer 1

The Correct Option is B

Concept: Level order traversal visits all nodes at the current depth before moving to nodes at the next depth level.
• BFS: Level order is a type of Breadth-First Search.
• Exploration: It processes nodes level-by-level, from top to bottom and left to right.

Step 1: Analyzing the traversal requirements.
To visit level 2, we must first store the children of all nodes at level 1. We need to process these children in the same order their parents were visited.

Step 2: Matching requirements to a data structure.
The First-In-First-Out (FIFO) property is required here. A Queue allows us to enqueue children as we visit parents.

Step 3: Tracing the process.
Start by putting the Root in the Queue. While the Queue is not empty, dequeue a node and enqueue its children. This ensures that all nodes at one level are handled before any node at the next level.