Tree Traversal Level Order BFS in DSA C - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: Imagine you have a family tree and you want to see the names generation by generation, starting from the oldest ancestor down to the youngest children.

🎯 Goal: You will build a simple binary tree and write code to print its nodes level by level using Breadth-First Search (BFS), also called level order traversal.

📋 What You'll Learn

Create a binary tree with 7 nodes having exact values: 1, 2, 3, 4, 5, 6, 7

Create a queue structure to help with BFS traversal

Implement the BFS level order traversal using the queue

Print the nodes in level order separated by spaces

💡 Why This Matters

🌍 Real World

Level order traversal is used in many real-world applications like printing organizational charts, finding shortest paths in networks, and scheduling tasks.

💼 Career

Understanding BFS and tree traversals is essential for software engineers working on data processing, game development, and system design.

1

Create the binary tree nodes

Create a struct called Node with an int data and two pointers left and right. Then create 7 nodes named n1 to n7 with data values 1 to 7 respectively. Connect them to form this tree:

1
/ \
2 3
/ \ / \
4 5 6 7

DSA C

// Define struct Node and create nodes n1 to n7 with data 1 to 7
// Connect nodes to form the tree
// Your code here

Hint

Think of each node as a person with a name (data) and pointers to their children (left and right).

2

Create a queue for BFS

Create a struct called Queue with an array of Node* called items of size 100, and two integers front and rear. Initialize a variable q of type Queue with front = 0 and rear = 0.

DSA C

#include 
#include 

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

typedef struct Queue {
    Node* items[100];
    int front;
    int rear;
} Queue;

int main() {
    Node n1 = {1, NULL, NULL};
    Node n2 = {2, NULL, NULL};
    Node n3 = {3, NULL, NULL};
    Node n4 = {4, NULL, NULL};
    Node n5 = {5, NULL, NULL};
    Node n6 = {6, NULL, NULL};
    Node n7 = {7, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;
    n3.right = &n7;

    Queue q;
    q.front = 0;
    q.rear = 0;

    // Your code here
}

Hint

The queue will help us remember which nodes to visit next in the tree.

3

Implement BFS level order traversal

Add functions enqueue and dequeue to add and remove Node* from the queue q. Then write a while loop that runs while q.front < q.rear. Inside the loop, dequeue a node, print its data, then enqueue its left and right children if they are not NULL. Start by enqueueing the root node &n1.

DSA C

#include 
#include 

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

typedef struct Queue {
    Node* items[100];
    int front;
    int rear;
} Queue;

void enqueue(Queue* q, Node* node) {
    q->items[q->rear++] = node;
}

Node* dequeue(Queue* q) {
    return q->items[q->front++];
}

int main() {
    Node n1 = {1, NULL, NULL};
    Node n2 = {2, NULL, NULL};
    Node n3 = {3, NULL, NULL};
    Node n4 = {4, NULL, NULL};
    Node n5 = {5, NULL, NULL};
    Node n6 = {6, NULL, NULL};
    Node n7 = {7, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.left = &n6;
    n3.right = &n7;

    Queue q;
    q.front = 0;
    q.rear = 0;

    enqueue(&q, &n1);

    while (q.front data);
        if (current->left != NULL) {
            enqueue(&q, current->left);
        }
        if (current->right != NULL) {
            enqueue(&q, current->right);
        }
    }

    // Your code here

    return 0;
}

Hint

Use the queue to visit nodes level by level. Print the node's data, then add its children to the queue.

4

Print the level order traversal output

Run the program to print the nodes in level order separated by spaces. The expected output is: 1 2 3 4 5 6 7

DSA C

#include 
#include 

// The full program is ready
// Run it to see the output
// Your code here

Hint

Run the program and check the printed output matches the expected level order traversal.

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