Level-order traversal (BFS) in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the order of nodes visited in BFS

Consider a binary tree where the root node is 1, its left child is 2, and right child is 3. Node 2 has children 4 and 5, and node 3 has children 6 and 7.

What is the order of nodes visited in a level-order traversal (BFS)?

A 1, 2, 3, 4, 5, 6, 7

B 1, 3, 2, 7, 6, 5, 4

C 4, 5, 6, 7, 2, 3, 1

D 1, 2, 4, 5, 3, 6, 7

💡 Hint

Level-order traversal visits nodes level by level from left to right.

In BFS, nodes are visited starting from the root, then all nodes at the next level from left to right, and so on. So the order is 1 (root), then 2 and 3 (level 2), then 4, 5, 6, 7 (level 3).

📋 Factual

intermediate

Queue usage in BFS

Which data structure is primarily used to implement level-order traversal (BFS) on a tree?

A Stack

B Hash Map

C Queue

D Priority Queue

💡 Hint

Think about the order nodes are visited and how to keep track of nodes to visit next.

BFS uses a queue to keep track of nodes to visit in the order they are discovered, ensuring nodes are processed level by level.

🚀 Application

advanced

Number of nodes visited at each level

Given a binary tree with 15 nodes perfectly balanced (each node has 0 or 2 children), how many nodes will BFS visit at level 3 (root is level 1)?

A 8

B 4

C 2

D 1

💡 Hint

Count nodes level by level in a perfect binary tree.

In a perfect binary tree, level 1 has 1 node, level 2 has 2 nodes, level 3 has 4 nodes, and level 4 has 8 nodes. Since the tree has 15 nodes, it has 4 levels. So level 3 has 4 nodes.

🔍 Analysis

advanced

Time complexity of BFS on a tree

What is the time complexity of performing a level-order traversal (BFS) on a tree with n nodes?

A O(n log n)

B O(log n)

C O(n^2)

D O(n)

💡 Hint

Consider how many times each node is visited and processed.

BFS visits each node exactly once and processes its children, so the total work is proportional to the number of nodes, which is O(n).

❓ Reasoning

expert

Effect of adding cycles on BFS traversal

Suppose you apply a BFS algorithm designed for trees on a graph that contains cycles but do not mark visited nodes. What will happen?

A The BFS will enter an infinite loop visiting nodes repeatedly.

B The BFS will visit each node exactly once as in a tree.

C The BFS will skip some nodes due to cycles.

D The BFS will terminate immediately without visiting any nodes.

💡 Hint

Think about what happens when nodes are revisited in a graph with cycles.

Without marking visited nodes, BFS will keep revisiting nodes in cycles endlessly, causing an infinite loop.