Mon. Oct 3rd, 2022

Hello Android

All android in one place

Binary Trees BFS Traversal In C++

3 min read

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 Trees BFS Traversal

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.

Breadth-First Algorithm in C++

#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;
}

// Breadth-First Search Algorithm
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);
}
Tree Class And Build Tree Function
Tree Class And Build Tree Function
BFS Algorithm Code
BFS Algorithm Code
Driver Function Code
Driver Function Code

Output

BFS Program Output
BFS Program Output

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/

www.hello-android.com

Leave a Reply

Your email address will not be published. Required fields are marked *

Hello android © All rights reserved. | Newsphere by AF themes.