Breadth-First Search (BFS)

A Level-Order Traversal Algorithm for Trees

Introduction

Breadth-First Search (BFS) is a tree traversal algorithm that visits all nodes level by level, starting from the root. It uses a queue to keep track of nodes that need to be visited, ensuring they are processed in the correct order for level-by-level exploration.

How BFS Works:

1

Start with the Root Node

  • Begin at the root of the tree and visit it first.
2

Use a Queue

  • Add the root node to a queue, which will help keep track of nodes to be visited.
3

Explore Level by Level

  • Remove the front node from the queue and visit it.
  • Add all its child nodes to the back of the queue.
4

Repeat Until Done

  • Continue this process until the queue is empty, meaning all nodes have been visited.

Implementation of Level Order Traversal (BFS)

//levelorderTraversal.cpp
#include <iostream>
#include <queue>
using namespace std;
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int data)
{
    this->data = data;
    this->left = NULL;
    this->right = NULL;
}
};
Node *buildTree(Node *root)
{
cout << "Enter The data: " << endl;
int data;
cin >> data;
root = new Node(data);
if (data == -1)
{
    return NULL;
}
cout << "Enter data for left : " << endl;
root->left = buildTree(root->left);
cout << "Enter data for right: " << endl;
root->right = buildTree(root->right);
return root;
}
void levelorderTraversal(Node *root)
{
queue<Node *> q;
q.push(root);
q.push(NULL);
while (!q.empty())
{
    Node *temp = q.front();
    q.pop();
    if (temp == NULL)
    {
        cout << endl;
        if (!q.empty())
        {
            q.push(NULL);
        }
    }
    else
    {
        cout << temp->data << " ";
        if (temp->left)
        {
            q.push(temp->left);
        }
        if (temp->right)
        {
            q.push(temp->right);
        }
    }
}
}
int main()
{
// creating tree
Node *root = NULL;
root = buildTree(root);

// lever order
levelorderTraversal(root);
}

Time Complexity

  • Time Complexity:O(n)
  • Every node is processed once, so the time complexity is proportional to the number of nodes (n).

Space Complexity

  • Space Complexity:O(n)
  • In the worst case, the queue can store all the nodes at the deepest level (up to n/2 nodes), so the space complexity is O(n).