# Binary Trees BFS Traversal In C++

Filed Under: C++ In this article, we will learn binary trees BFS traversal in C++. Binary trees are very commonly used data structures in real-life. Be it the file manager or the recursion tree of an algorithm, you will always find trees there. This marks the importance of the tree data structure in our lives. Breadth-First Search(BFS) is a special kind of traversal over trees that we are going to discuss very soon.

## What Is A Binary Tree?

Let me very quickly give you a brief introduction to binary trees. Binary trees are special kind of trees that contains only two children at the maximum, a left child and a right child. These trees are of special importance because using binary trees we can derive the binary search trees(BST). Binary search trees are very useful for sorting and storing hierarchically sorted data.

## What Is Breadth-First Search(BFS) Traversal?

In this kind of traversal of a binary tree, we start from the root node and move downwards by printing all the nodes at each level. Sometimes we call this traversal as `level order traversal`.

Below is an example to demonstrate the working of the BFS algorithm on a tree.

## Binary Tree BFS Traversal Algorithm

Let’s go through this algorithm in a set of small atomic steps. These steps when executed in order will work as the breadth-first search algorithm. Imagine that you are standing at the topmost floor of a multistorey building, then you start moving down and keep noting all the room numbers into separate lines for each floor.

1. We use a queue to store the nodes of the tree.
2. In the starting we insert the root node into the queue and a NULL pointer after the root node to denote the end of this level.
3. Then we begin a while loop and implement the following logic,
• This while loop will run until the queue becomes empty
• Extract the front most node of the queue
• if this node is NULL i.e. a NULL pointer, print a newline character on the screen because this value marks the end of a particular level
• Now we remove this node from the queue, and check if the queue becomes empty or not
• If the queue is still not empty then we insert another NULL pointer into the queue
• Otherwise, check if the root has a left child, if it exists then push it into the queue
• Similarly check for the right child and push it into the queue if it exists.

This is basically it, it might seem a little complex in the beginning. Trust me it is not, in fact, it’s incredibly simple once you have understood the algorithm. Let’s quickly jump to the C++ code for this algorithm.

```#include <iostream>
#include <queue>

using namespace std;

// tree class
class Node
{
public:
int data;
Node* left;
Node* right;

// constructor for a new tree node
// insert the data
// initialize the left and the right
// subtrees with NULL
Node(int data): data(data), left(NULL), right(NULL) {}
};

// function to build the tree
Node* build_preorder()
{
// input an element
int ele;
cin >> ele;

// base case
if(ele == -1)
return NULL;

// first insert the data
// into the root
Node* root = new Node(ele);

// now build the left subtree
root->left = build_preorder();

// similarly the right subtree
root->right = build_preorder();

// finally return the root
return root;
}

void BFS(Node* root)
{
cout << "The BFS traversal of the tree is:" << endl;

// queue to store the nodes
queue <Node*> q;

// pushing root and NULL into the queue
q.push(root);
q.push(NULL);

// this while loop will run until
// the queue becomes empty
while(!q.empty())
{
// extract the front most node
Node *f = q.front();

// pop this node out of the queue
// because this node is no longer
// needed
q.pop();

if(f == NULL)
{
// print a newline
cout << endl;

// check if the queue becomes
// empty, if not then insert
// another NULL character
if(!q.empty())
q.push(NULL);
}
else
{
// if the front node is not
// a NULL pointer, print the
// data
cout << f->data << " ";

// check for the left child
// if found, then insert it
// into the queue
if(f->left)
q.push(f->left);

// check for the right child
// if there, then insert it
// into the queue
if(f->right)
q.push(f->right);
}
}
}

// main function to drive the program
int main()
{
cout << "Enter the elements of the tree in pre-order manner" << endl;

// building the tree
Node *root = build_preorder();

// calling the BFS function
BFS(root);
}
```

## Conclusion

Today we learned binary trees BFS traversal in C++. We also discussed, in brief, the binary trees. Then we moved to the breadth-first search algorithm. In the end, we developed a C++ program that demonstrates the BFS algorithm for binary trees. That’s all for now, thanks for reading.

https://www.cprogramming.com/tutorial/lesson18.html

https://www.geeksforgeeks.org/binary-tree-set-1-introduction/

close
Generic selectors
Exact matches only
Search in title
Search in content