Tree Traversal Level Order BFS in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the queue node pointer for BFS traversal.

DSA C

struct Node* [1] = NULL;

Drag options to blanks, or click blank then click option'

Atemp

Broot

CqueueNode

Dcurrent

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'root' which is the tree root, not the queue node.

Using 'temp' or 'current' which are used later, not for queue declaration.

We declare a pointer named queueNode to use as the queue node in BFS.

2fill in blank

medium

Complete the code to enqueue the root node into the queue.

DSA C

enqueue(queue, [1]);

Drag options to blanks, or click blank then click option'

ANULL

BqueueNode

Ctemp

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Enqueuing NULL which causes no traversal.

Enqueuing temp or queueNode which are used later.

We enqueue the root node to start BFS traversal.

3fill in blank

hard

Fix the error in the condition to check if the queue is empty.

DSA C

while (queue->front != [1]) {

Drag options to blanks, or click blank then click option'

ANULL

Bqueue->front

C-1

Dqueue->rear

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing front to rear which is incorrect for empty check.

Using -1 which is not a pointer value.

The queue is empty when front is NULL.

4fill in blank

hard

Fill both blanks to correctly assign left and right children to the queue.

DSA C

if (temp->left != [1]) enqueue(queue, temp->left);
if (temp->right != [2]) enqueue(queue, temp->right);

Drag options to blanks, or click blank then click option'

ANULL

Broot

Ctemp

Dqueue

Attempts:

3 left

💡 Hint

Common Mistakes

Checking against root or temp which are not child pointers.

Using queue which is the queue structure, not a node pointer.

We check if left and right children are not NULL before enqueuing.

5fill in blank

hard

Fill all three blanks to dequeue the current node and print its data.

DSA C

[2] = dequeue(queue);
[3] = [2];
printf("%d ", [1]->data);

Drag options to blanks, or click blank then click option'

Atemp

BqueueNode

Droot

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing temp and queueNode in wrong order.

Printing or dequeuing wrong variables.

We dequeue into queueNode, assign temp to queueNode, then print queueNode data.

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