Tree Traversals: Breadth-First Search (BFS)

March 9, 2023

Tree Traversals: Breadth First Search (BFS)

The term traversal means to visit each node in a tree exactly once. In linear lists the order of traversal is vividly first to last. However, in trees there exists no such natural linear order.In Tree Traversal : Breadth-First Search (BFS) article, breadth first search is studied.

More Information About BFS:

BFS can be defined as an algorithm dedicated to traversing a tree structure, level by level or depth by depth.
This category of tree traversal initializes from the root node and explores all the adjacent nodes on a current level and then moves on to the next level, and so on.

Why Queue is better to traverse than Recursion?

Queues improves the time complexity because recursion gives the time complexity of O(2^n) in the worst case, whereas queue gives time complexity of O(n).
Height of the tree is first calculated to print level order but this is not required in queue.
Implementation is shorter in queues.

Algorithm (Queue):

If the root is NULL, return.
Otherwise push the root in queue.
Print the node’s data and add its left and right child.
Pop the node from the queue.
Repeat until the queue is empty.

Algorithm (Recursion):

Calculate height of tree.
Initialize loop from 0 to height
Recursive call for left and right subtree and decrease level by 1.
If level is 0, print the nodes

BST: Search in a Binary Search Tree

BST: Insertion in a Binary Search Tree

BST: Deletion in a Binary Search Tree

Traversals in Tree

Tree Traversals: Depth First Search (DFS)

Code Implementation for Tree Traversal : Breadth-First Search (BFS) in C++

Run

#include<bits/stdc++.h>
using namespace std;

struct TreeNode
{
  int val;
  TreeNode *left;
  TreeNode *right;
    TreeNode (int x):val (x), left (NULL), right (NULL)
  { }
};

void bfs (TreeNode * root)
{
  queue q;
  q.push (root);

  while (!q.empty ())
    {
      int num_nodes = q.size ();

      for (int i = 0; i < num_nodes; i++)
	{
	  TreeNode *curr_node = q.front ();
	  q.pop ();

	  cout << curr_node->val << " ";

	  if (curr_node->left)
	    {
	      q.push (curr_node->left);
	    }
	  if (curr_node->right)
	    {
	      q.push (curr_node->right);
	    }
	}
    }
}

int main ()
{
  TreeNode *root = new TreeNode (10);
  root->left = new TreeNode (20);
  root->right = new TreeNode (30);
  root->left->left = new TreeNode (40);
  root->left->right = new TreeNode (50);
  cout<<"BFS Traversal of the tree is : ";
  bfs (root);

  return 0;
}

Output:

10 20 30 40 50

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal Line by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric – C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree- C | C++ | Java