Master Level Order Traversal: BFS Approach in Binary Trees

A binary tree can be explored level by level using level order traversal, which begins at the root node and proceeds downward. In order to visit every node at a given depth before moving on to the next, it follows a left-to-right pattern at each level.

Example Binary Tree:

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

Level Order Traversal Output:

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

How Level Order Traversal Works?

1. Begin at the root: Start the traverse at level 0, which is the highest node.
2. Visit Nodes by Level: Process each node at the current depth before moving on to the next level. 
3. Use a Queue for Efficient Traversal: Since nodes must be processed in a specific order, a queue is used to store nodes temporarily and access them sequentially.
4. Follows Breadth-First Search (BFS) Principles: Unlike depth-first search (DFS), which explores one branch fully before moving to another, level order traversal explores all nodes at a given depth first.

Level order traversal is built on two key concepts: the structure of binary tree levels and the breadth-first search (BFS) paradigm.

Levels in a Binary Tree

In a binary tree, each node has a certain "level" that indicates how far it is from the root node. The root is at level 0. Its immediate offspring are at level 1, their offspring are at level 2, and so on. Nodes may be grouped and processed based on how close they are to the root due to this tiered structure.

Tree Height

The total number of edges in the most lengthy path connecting a binary tree's root and leaf nodes is its height. The height of a tree tells how many levels you have to go through from the top to the bottom. Height is especially important to know in cases of recursion since it tells you how many times the process of traversal has to be repeated to cover all the levels.

Breadth-First Search (BFS) Paradigm

If you remember, depth-first search tries to completely expand one branch of the tree before moving to another branch; breadth-first search, on the other hand, explores the tree level by level, starting from the root. This is accomplished using a queue, which ensures nodes are processed in the correct order, starting from the root and progressing outward level by level.

Why These Concepts Matter

Level order traversal ensures that each node is visited according to its distance from the root by grouping nodes into levels and utilizing BFS. This property makes it especially useful for tasks that require processing nodes based on their hierarchical position, such as finding the shortest path or analyzing tree structure.

When working with trees, there are two main methods to go through all the nodes level by level:

Approach 1: Recursive Method (Using Height Calculation)

The binary tree's hierarchical structure and the idea of utilizing recursion to process nodes level by level are the foundation of the recursive approach for level order traversal. The recursive method makes use of the call stack to handle traversal across tree levels, in contrast to the iterative method, which employs a queue for breadth-first exploration.

Algorithm Steps:

• Find the binary tree's height.
• Repeat from level 1 to the height of the tree.
• At every level, print nodes recursively.

Code Example:

#include <stdio.h>
#include <stdlib.h>

// Structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int treeHeight(struct Node* root) {
    if (!root) return 0;
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Function to print nodes at a given level
void printLevel(struct Node* root, int level) {
    if (!root) return;
    if (level == 1) 
        printf("%d ", root->data);
    else {
        printLevel(root->left, level - 1);
        printLevel(root->right, level - 1);
    }
}

// Function to perform level order traversal
void levelOrderTraversal(struct Node* root) {
    int height = treeHeight(root);
    for (int i = 1; i <= height; i++) {
        printLevel(root, i);
    }
}

// Driver code
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    
    printf("The Level Order Traversal is: ");
    levelOrderTraversal(root);
    return 0;
}

Code Explanation:

The program builds a binary tree and uses recursion to carry out level order traversal. The tree height is calculated first. Recursive calls are then used to print nodes at each level. This method guarantees that nodes are shown from left to right and top to bottom.

Output:

The Level Order Traversal is: 1 2 3 4 5 6 

Time And Space Complexity:

• Since each level's nodes are visited several times, the worst-case time complexity is O(n²).
• Because of recursive calls in the function stack, the space complexity is O(h), where h is the tree's height.

Approach 2: Queue-Based Iterative Method (Optimal Approach)

This method outputs nodes one level at a time in a methodical manner using a queue. The recursive technique ultimately recalculates certain elements in a cycle, which is not ideal, but both iterative and recursive procedures traverse the same tree. However, the iterative method makes precisely one visit to each node.

Algorithm Steps:

• Initialize a queue and insert the root node.
• Process nodes iteratively as dequeue a node and printing its value. Add its left and right children to the queue if they are present.
• Repeat until the queue is empty.

Code Example:

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100  // Define maximum queue size

// Structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function for level order traversal using a queue
void levelOrderTraversal(struct Node* root) {
    if (!root) return;

    struct Node* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;
    
    queue[rear++] = root; // Enqueue root

    while (front < rear) {
        struct Node* temp = queue[front++]; // Dequeue
        printf("%d ", temp->data);

        if (temp->left) queue[rear++] = temp->left;  // Enqueue left child
        if (temp->right) queue[rear++] = temp->right; // Enqueue right child
    }
}

// Driver code
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    
    printf("The Level Order Traversal is: ");
    levelOrderTraversal(root);
    return 0;
}

Code Explanation:

This program constructs a binary tree and performs level order traversal using a queue. The queue helps process each node in the correct order (from left to right, level by level). Nodes are dequeued, and their children are added to the queue until all levels are processed.

Output:

The Level Order Traversal is: 1 2 3 4 5 6 

Time And Space Complexity:

• Time Complexity: Because each node is processed only once, the time complexity is O(n).
• Space Complexity: The space complexity is O(n) in the worst-case scenario, where all nodes are kept in the queue, e. g., in a full binary tree.

Understanding the level order traversal's applicability for various binary tree architectures requires analyzing its efficiency. The two primary approaches—recursive and iterative (queue-based)- differ significantly in their time and space complexity.

Iterative (Queue-Based) Approach

Time Complexity:

Each node is processed precisely once by the iterative technique using a queue. Each node in a binary tree with n nodes is enqueued and dequeued once, for a total of O(n) operations. As a result, the total time complexity is O(n).

Space Complexity:

The space required depends on the maximum number of nodes held in the queue at any point, which is determined by the tree's maximum width (w).

• Best Case (Skewed Tree): The queue holds at most one node at a time, so space complexity is O(1).
• Worst Case (Complete/Full Tree): The queue may hold up to half of the nodes (the entire last level), leading to O(n) space usage.

Summary:

• Time Complexity: O(n)
• Space Complexity: O(w), where w is the maximum width of the tree (O(n) worst case).

Recursive Approach (Using Height Calculation)

Time Complexity:

This method first calculates the tree's height and then prints nodes at each level recursively. For each level, the algorithm traverses the tree to collect nodes at that level.

• Each node may be visited more than once in the worst case (extremely skewed or imbalanced trees), which would result in a time complexity of O(n).

Space Complexity:

The height of the tree (h) and the greatest depth of the recursion stack determine how much space is used.

• Space Complexity: O(h)

Summary:

• Time Complexity: O(n²) (worst case)
• Space Complexity: O(h), whereas h is the height of the tree.

Comparative Table

Practical Implications

• Generally speaking, an iterative approach is favoured when dealing with large or balanced trees since it has linear time complexity and it can efficiently use space in most situations.
• On the other hand, a recursive approach might be less efficient in the case of large or skewed trees, but could be okay for small or shallow trees if one wants to keep it simple.

When choosing the optimal traversal technique for a specific binary tree structure, it is helpful to be aware of these intricacies.

Approach 1: Using Level Delimiters

This method prints each level of the binary tree on a new line by using a special delimiter (NULL) in the queue.

Algorithm Steps:

• Initialize a queue and insert the root node.
• Use NULL as a level marker to indicate the end of a level.
• Process nodes iteratively as dequeue a node and print its value. Add the left and right children to the queue if they are available. Print a newline and enqueue another NULL (if there are still nodes) if a NULL is dequeued.
• Continue until there are no more people in line.

Code Example:

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100  // Define maximum queue size

// Structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function for level order traversal using level delimiters
void printLevelWise(struct Node* root) {
    if (!root) return;

    struct Node* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = root;
    queue[rear++] = NULL; // Level delimiter

    while (front < rear) {
        struct Node* temp = queue[front++];

        if (temp == NULL) {  // End of a level
            printf("\n");
            if (front < rear) queue[rear++] = NULL; // Add delimiter if more nodes exist
        } else {
            printf("%d ", temp->data);
            if (temp->left) queue[rear++] = temp->left;
            if (temp->right) queue[rear++] = temp->right;
        }
    }
}

// Driver code
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    
    printf("Level Order Traversal (Each Level on New Line):\n");
    printLevelWise(root);
    return 0;
}

Code Explanation:

By building a binary tree and doing level order traversal, this program makes sure that every level is written on a different line. After every level, a queue is employed, and NULL is added as a marker. If more nodes are present, an additional NULL is appended as a marker and a newline is written when NULL is found.

Output:

Level Order Traversal (Each Level on New Line):
1 
2 3 
4 5 6 

Time And Space Complexity:

• O(n) is the time complexity.
• When all nodes are kept in the queue, the worst-case space complexity is O(n).

Approach 2: Using Two Queues

This method efficiently prints each level of the binary tree on a new line using two queues. One queue stores the current level, while the second queue stores the next level.

Algorithm Steps:

• Initialize two queues: the current level's nodes are stored in currentQueue. The following level's nodes are stored in nextQueue.
• Process nodes iteratively: Nodes from the currentQueue are printed and dequeued. Put their kids in the next queue. Print a newline and switch queues when currentQueue is empty.
• Repeat until all levels are processed.

Code Example:

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100  // Define maximum queue size

// Structure for a tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Function to create a new node
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function for level order traversal using two queues
void printLevelOrderLineByLine(struct Node* root) {
    if (!root) return;

    struct Node* currentQueue[MAX_QUEUE_SIZE];
    struct Node* nextQueue[MAX_QUEUE_SIZE];

    int currentFront = 0, currentRear = 0;
    int nextFront = 0, nextRear = 0;
    
    currentQueue[currentRear++] = root; // Start with root in current queue

    while (currentFront < currentRear) {
        struct Node* temp = currentQueue[currentFront++];
        printf("%d ", temp->data);

        if (temp->left) nextQueue[nextRear++] = temp->left;
        if (temp->right) nextQueue[nextRear++] = temp->right;

        // If current queue is empty, move to the next level
        if (currentFront == currentRear) {
            printf("\n");
            currentFront = 0; 
            currentRear = nextRear;
            
            for (int i = 0; i < nextRear; i++) {
                currentQueue[i] = nextQueue[i]; // Copy nextQueue to currentQueue
            }
            nextRear = 0; // Reset next queue
        }
    }
}

// Driver code
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    
    printf("Level Order Traversal (Each Level on New Line):\n");
    printLevelOrderLineByLine(root);
    return 0;
}

Code Explanation:

The program generates a binary tree and outputs its level order traversal, with each level appearing on a new line. CurrentQueue is used for the current level, while nextQueue is used for the subsequent level. Traversal proceeds smoothly when the currentQueue runs out and is replaced with nextQueue.

Output:

Level Order Traversal (Each Level on New Line):
1 
2 3 
4 5 6 

Time And Space Complexity:

• Time Complexity: O(n), so every node is handled just once.
• Space Complexity: Because two queues are used to store nodes at each level, the space complexity is O(n).

By using practice problems to apply level order traversal ideas, typical application cases are revealed, and comprehension is strengthened. The activities that follow cover both iterative (BFS) and recursive techniques, ranging from basic implementations to imaginative applications.

1. Basic Level Order Traversal

Problem:

Given a binary tree, print its nodes in level order (from top to bottom, left to right).

C Code Example:

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 100

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void levelOrderTraversal(struct Node* root) {
    if (!root)
        return;

    struct Node* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = root;

    while (front < rear) {
        struct Node* temp = queue[front++];
        printf("%d ", temp->data);

        if (temp->left)
            queue[rear++] = temp->left;

        if (temp->right)
            queue[rear++] = temp->right;
    }
}

// Usage example
// struct Node* root = createNode(1);
// root->left = createNode(2);
// root->right = createNode(3);
// levelOrderTraversal(root);

2. Level Order Traversal Using Recursion

Problem:

Use recursion for executing level order traversal of a binary tree (without an explicit queue).

C Code Example:

int treeHeight(struct Node* root) {
    if (!root)
        return 0;

    int left = treeHeight(root->left);
    int right = treeHeight(root->right);

    return (left > right ? left : right) + 1;
}

void printLevel(struct Node* root, int level) {
    if (!root)
        return;

    if (level == 1)
        printf("%d ", root->data);
    else {
        printLevel(root->left, level - 1);
        printLevel(root->right, level - 1);
    }
}

void recursiveLevelOrder(struct Node* root) {
    int h = treeHeight(root);

    for (int i = 1; i <= h; i++)
        printLevel(root, i);
}

3. Print Each Level on a New Line

Problem:

Modify your level order traversal so that nodes at each level are printed on a separate line.

C Code Example (with delimiter):

void printLevelWise(struct Node* root) {
    if (!root)
        return;

    struct Node* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = root;
    queue[rear++] = NULL;  // Level delimiter

    while (front < rear) {
        struct Node* temp = queue[front++];

        if (temp == NULL) {
            printf("\n");

            if (front < rear)
                queue[rear++] = NULL;
        } else {
            printf("%d ", temp->data);

            if (temp->left)
                queue[rear++] = temp->left;

            if (temp->right)
                queue[rear++] = temp->right;
        }
    }
}

4. Find the Level with Maximum Nodes

Problem:

Find the level with the most nodes in a binary tree and return the index of that level.

C Code Example:

int maxLevelNodes(struct Node* root) {
    if (!root)
        return -1;

    struct Node* queue[MAX_QUEUE_SIZE];
    int front = 0, rear = 0;

    queue[rear++] = root;

    int maxNodes = 0, level = 0, maxLevel = 0;

    while (front < rear) {
        int count = rear - front;

        if (count > maxNodes) {
            maxNodes = count;
            maxLevel = level;
        }

        for (int i = 0, n = count; i < n; i++) {
            struct Node* temp = queue[front++];

            if (temp->left)
                queue[rear++] = temp->left;

            if (temp->right)
                queue[rear++] = temp->right;
        }

        level++;
    }

    return maxLevel;
}

5. Count Nodes at a Specific Level

Problem:

Create a function that returns the number of nodes in the binary tree at a specific level, k.

C Code Example:

int countNodesAtLevel(struct Node* root, int k) {
    if (!root)
        return 0;

    if (k == 1)
        return 1;

    return countNodesAtLevel(root->left, k - 1) +
           countNodesAtLevel(root->right, k - 1);
}

6. Reverse Level Order Traversal

Problem:

Within each level, print the binary tree's nodes from left to right and from bottom to top in reverse level order.

C Code Example:

void reverseLevelOrder(struct Node* root) {
    if (!root)
        return;

    struct Node* queue[MAX_QUEUE_SIZE];
    struct Node* stack[MAX_QUEUE_SIZE];
    int front = 0, rear = 0, top = -1;

    queue[rear++] = root;

    while (front < rear) {
        struct Node* temp = queue[front++];
        stack[++top] = temp;

        if (temp->right)  // right first
            queue[rear++] = temp->right;

        if (temp->left)
            queue[rear++] = temp->left;
    }

    while (top >= 0) {
        printf("%d ", stack[top--]->data);
    }
}

Note:

The purpose of the practice problems that follow is to help you better grasp level order traversal principles. Each problem includes a clear description and a sample C code solution to help you apply what you’ve learned and build confidence in implementing different traversal scenarios.

This table clearly compares level order traversal with depth-first traversal, helping in selecting the appropriate traversal technique based on problem requirements and tree structure.

Level order traversal is not only fundamental for exploring binary trees but also serves as the backbone for several practical applications. Here are some of the most common and valuable use cases:

1. Finding the Level (Depth) of a Node

The best method for figuring out the level (or depth) at which a certain node appears in a binary tree is level order traversal. You may quickly determine the level where the target node is located by going level by level through the tree and inspecting each node.

How it works:

• Begin from the root node at level 1.
• Traverse each level, incrementing a level counter as you move downward.
• At each level, check if any node matches the target value.
• If found, return the current level number.

Use case:

This is useful in scenarios where you need to determine the relationship between nodes, such as finding the generation of a member in a family tree or the depth of a node in hierarchical data.

2. Counting the Number of Nodes at a Specific Level

Counting the number of nodes at a specific level is another common use. When examining a tree's structure, such as determining its maximum width or allocating jobs in hierarchical systems, this information is useful.

How it works:

• Traverse the tree level by level.
• When you reach the desired level, count the number of nodes present at that level.

Use case:

This is important for tasks like:

• Calculating the width of a tree at a certain depth.
• Distributing resources evenly across levels in a hierarchy.
• Assessing the balance of a tree.

3. Printing Nodes Level by Level (Line by Line)

Level order traversal is often used to print or process nodes level by level, which is helpful for visualization, debugging, or exporting tree structures.

Use case:

• Displaying hierarchical data in a readable format.
• Visualizing the breadth of a tree for educational or diagnostic purposes.

4. Finding the Shortest Path in Unweighted Trees

Since level order traversal visits nodes in increasing order of their distance from the root, it naturally finds the shortest path from the root to any node in an unweighted tree.

Use case:

• Solving problems where the minimum number of steps or connections is required, such as in networking or game AI.

5. Other Practical Scenarios

Level order traversal is also used in:

• Computing the maximum width of a binary tree.
• Finding nodes that are a specific distance out from the root.
• Performing level-based operations in decision trees or organizational charts.

Bottom Line

As level order traversal may handle nodes based on how far they are from the root, it is essential for a variety of tree-related issues and practical uses.

By processing nodes level by level, level order traversal provides an organized and understandable method of navigating binary trees. Level order traversal offers a clear and structured way to navigate binary trees by processing nodes level by level. By leveraging a queue and following the breadth-first search approach, it ensures that nodes are visited in order of their distance from the root.

Compared to depth-first traversals, level order traversal excels in scenarios that require level-based processing, shortest path discovery, or hierarchical analysis. The queue-based iterative approach is still the most effective and useful, even though recursive methods aid in understanding the idea.

Gaining proficiency in this traversal improves your comprehension of trees and gets you ready for both theoretical and practical algorithmic problems.

Points to Remember 

1. Level order traversal follows BFS, not DFS, and always processes nodes level by level.
2. A queue is essential because it preserves the correct visiting order of nodes.
3. With O(n) time complexity, the iterative queue-based method is the best.
4. Although conceptually helpful, recursive level order traversal is less effective for huge trees.
5. Decision trees, hierarchical data structures, and shortest path issues all frequently employ this traversal.

1. What is level order traversal in a binary tree?

Visiting every node in a binary tree level by level, beginning at the root and working down to each level after that, is known as level order traversal. Nodes are usually processed from left to right at each level.

2. Is level order traversal the same as Breadth-First Search (BFS)?

Yes, a particular use of Breadth-First Search (BFS) for trees is level order traversal. In order to ensure that every node at a certain depth gets visited before going on to the next, both employ a queue to process nodes level by level.

3. What data structure is typically used for level order traversal?

A queue is used because it allows nodes to be processed in the order they are discovered, which matches the left-to-right, level-by-level requirement of level order traversal.

4. Can level order traversal be implemented recursively?

Yes, but the recursive approach is less efficient. It usually involves first calculating the height of the tree and then printing nodes at each level recursively, resulting in a worst-case time complexity of O(n²).

5. Does level order traversal always process nodes left to right at each level?

By convention, nodes at each level are processed from left to right. However, unless a specific order is required by the problem, the main requirement is visiting all nodes at each level before moving to the next.

6. What happens if the tree is empty?

If the binary tree is empty (the root is null), level order traversal does nothing, as there are no nodes to process.

7. How does level order traversal behave with unbalanced or skewed trees?

Level order traversal works for any binary tree structure, balanced or unbalanced. However, in skewed trees (where nodes are only on one side), the queue may contain fewer nodes at each level, and the traversal essentially proceeds down a single path.

8. When should I use level order traversal?

Use level order traversal when you need to process nodes by their distance from the root or when level-based information is required (such as printing nodes level by level or finding the shortest path in an unweighted tree).