Tree Traversal Level Order BFS in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this level order traversal?

Given the binary tree below, what is the printed output of a level order traversal (BFS)?

Tree structure:
10
/ \
5 15
/ \ \
3 7 18

DSA C

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void levelOrder(struct Node* root) {
    if (!root) return;
    struct Node* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        struct Node* current = queue[front++];
        printf("%d ", current->data);
        if (current->left) queue[rear++] = current->left;
        if (current->right) queue[rear++] = current->right;
    }
}

A 10 5 15 3 7 18

B 3 7 5 18 15 10

C 10 15 5 18 7 3

D 5 3 7 10 15 18

💡 Hint

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

Level order traversal uses a queue to visit nodes starting from the root, then its children from left to right, then their children, and so on. So the output is 10 (root), then 5 and 15 (level 2), then 3, 7, and 18 (level 3).

🧠 Conceptual

intermediate

What data structure is essential for level order traversal?

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

A Priority Queue

B Stack

C Queue

D Hash Map

💡 Hint

Think about the order nodes are visited in BFS.

A queue is used because it follows First-In-First-Out (FIFO) order, which matches the level order traversal visiting nodes level by level.

🔧 Debug

advanced

Why does this level order traversal code cause an infinite loop?

Consider this code snippet for level order traversal. Why does it cause an infinite loop?

Code snippet:
int front = 0, rear = 0;
queue[rear++] = root;
while (front <= rear) {
Node* current = queue[front++];
printf("%d ", current->data);
if (current->left) queue[rear++] = current->left;
if (current->right) queue[rear++] = current->right;
}

A The condition should be 'front < rear' instead of 'front <= rear'.

B The queue array is not large enough to hold all nodes.

C The root node is not added to the queue initially.

D The current node is not dequeued properly.

💡 Hint

Check the loop condition carefully.

Using 'front <= rear' causes the loop to run one extra time when front equals rear, leading to accessing an invalid queue element and possibly infinite loop. The correct condition is 'front < rear'.

❓ Predict Output

advanced

What is the output of this modified level order traversal?

This code prints nodes level by level but prints a newline after each level. What is the output?

Tree:
1
/ \
2 3
/ / \
4 5 6

Code snippet:
void levelOrderNewline(Node* root) {
if (!root) return;
Node* queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
int count = rear - front;
for (int i = 0; i < count; i++) {
Node* current = queue[front++];
printf("%d ", current->data);
if (current->left) queue[rear++] = current->left;
if (current->right) queue[rear++] = current->right;
}
printf("\n");
}
}

A 1 2 3 \n 4 5 6 \n

B 1 2 3 4 5 6 \n

C 1 \n 2 3 4 5 6 \n

D 1 \n 2 3 \n 4 5 6 \n

💡 Hint

Each level is printed on its own line.

The code prints nodes level by level. First level: 1, second level: 2 3, third level: 4 5 6, each followed by a newline.

🧠 Conceptual

expert

What is the time complexity of level order traversal on a binary tree with n nodes?

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

A O(n log n)

B O(n)

C O(log n)

D O(n^2)

💡 Hint

Each node is visited exactly once.

Level order traversal visits each node once and processes its children, so the time complexity is linear in the number of nodes, O(n).

Practice

1. What does the Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in preorder (root, left, right)

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in inorder (left, root, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand BFS traversal

   Level Order Traversal visits nodes level by level, starting from the root and moving down each level from left to right.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder are depth-first traversals, not level order.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level Order = BFS = top to bottom, left to right [OK]

Hint: Level order means visit nodes by levels, not depth [OK]

Common Mistakes:

• Confusing BFS with preorder traversal
• Thinking BFS visits nodes depth-first
• Mixing up traversal orders

2. Which of the following is the correct way to initialize a queue for BFS in C?

easy

A. struct Queue q; initializeQueue(&q); // Using struct and init function

B. queue<int> q; // C++ style, not C

C. int q[]; // array declaration without size

D. Queue q = new Queue(); // Java style, not C

Solution

1. Step 1: Identify correct C syntax for queue

   C uses structs and functions to create and initialize queues, not C++ or Java syntax.

2. Step 2: Analyze options

   struct Queue q; initializeQueue(&q); // Using struct and init function shows struct usage with an initialization function, which is correct in C. Others use C++ or Java syntax or invalid declarations.

3. Final Answer:

   struct Queue q; initializeQueue(&q); // Using struct and init function -> Option A

4. Quick Check:

   C queue needs struct + init function [OK]

Hint: Use struct and init function for queue in C [OK]

Common Mistakes:

• Using C++ or Java syntax in C code
• Declaring arrays without size
• Not initializing the queue properly

3. Given the binary tree:

    1
   / \
  2   3
 / \
4   5

What is the output of the level order traversal (BFS)?

medium

A. [1, 2, 3, 4, 5]

B. [1, 3, 2, 4, 5]

C. [4, 5, 2, 3, 1]

D. [2, 4, 5, 1, 3]

Solution

1. Step 1: Start from root and enqueue nodes level-wise

   Start with root 1, then enqueue its children 2 and 3.

2. Step 2: Visit nodes in queue order

   Visit 1, then 2 and 3, then children of 2 which are 4 and 5.

3. Final Answer:

   [1, 2, 3, 4, 5] -> Option A

4. Quick Check:

   Level order visits nodes by levels: 1, then 2 & 3, then 4 & 5 [OK]

Hint: Visit nodes level by level, left to right [OK]

Common Mistakes:

• Swapping order of children
• Confusing BFS with DFS orders
• Listing nodes in reverse order

4. Consider this C code snippet for level order traversal:

void levelOrder(struct Node* root) {
    if (!root) return;
    struct Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        struct Node* curr = dequeue(&q);
        printf("%d ", curr->data);
        if (curr->left) enqueue(&q, curr->left);
        if (curr->right) enqueue(&q, curr->right);
    }
}

What is the likely bug if the output is empty?

medium

A. The printf statement is missing a newline

B. The enqueue function does not add nodes correctly

C. The root node is NULL

D. Queue is not initialized properly before use

Solution

1. Step 1: Check the early return condition

   The function has if (!root) return; which skips all printing if root is NULL, leading to empty output.

2. Step 2: Verify other possibilities

   Queue is initialized properly with initQueue(&q); printf missing newline wouldn't cause empty output; enqueue issues are possible but less direct than NULL root.

3. Final Answer:

   The root node is NULL -> Option C

4. Quick Check:

   if (!root) return; causes empty output [OK]

Hint: Check if root is NULL before traversal [OK]

Common Mistakes:

• Overlooking the NULL root check
• Assuming the tree always has a valid root
• Focusing on queue when init is present

5. You want to print the level order traversal of a binary tree but separate each level on a new line. Which modification is needed in the BFS algorithm?

hard

A. Use recursion to print nodes level by level

B. Use two stacks instead of a queue

C. Perform inorder traversal and print newline after each node

D. Use a queue and track the number of nodes at current level to print newline after each level

Solution

1. Step 1: Understand level separation in BFS

   To print each level on a new line, track how many nodes are in the current level before processing them.

2. Step 2: Implement counting nodes per level

   Use the queue size at start of each level to know how many nodes to print before printing a newline.

3. Step 3: Analyze other options

   Two stacks are for DFS variants, inorder traversal is not level order, recursion for level order is inefficient and complex.

4. Final Answer:

   Use a queue and track the number of nodes at current level to print newline after each level -> Option D

5. Quick Check:

   Count nodes per level in queue to print newlines [OK]

Hint: Count nodes in queue per level to print newlines [OK]

Common Mistakes:

• Using stacks instead of queue for BFS
• Confusing inorder with level order
• Trying recursion for level order printing