GATE CS 2004 Q6 — Trees

Level order traversal visits the nodes of a tree level-by-level, starting from the root (level 0), then all nodes at level 1, then level 2, and so on.

Let's analyze the given options:

• Breadth First Search (BFS): BFS is a graph traversal algorithm that starts at a designated source node and explores all of its neighboring nodes at the present depth level before moving on to the nodes at the next depth level. When applied to a rooted tree starting from the root, BFS visits nodes level-by-level, which is precisely a level order traversal.
• Depth First Search (DFS): DFS explores as deep as possible along each branch before backtracking. Preorder and in-order traversals are specific types of depth-first traversals. They do not visit nodes level-by-level.

Therefore, level order traversal is equivalent to performing a breadth first search starting from the root.