Breadth First Search Tree Traversal

Written by

studymite

Breadth-First Search Traversal of a Tree

For breadth-first traversal, we will use a queue. We will first push a node to it and for each node in front, we’ll check if its left and right child exist if yes then push it to the queue, and in the next iteration pop front and print it.

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

struct Node{ int data; Node* left; Node* right; Node(int data){ this->data = data; left = right = NULL; } };

void bfs(Node* root){ if(root == NULL) return; queue<Node*> q; q.push(root); while(!q.empty()){ int size = q.size();

  	for(int i = 0; i &lt; size; i++){
    	Node* curr = q.front();
      	q.pop();
      	cout&lt;&lt;curr-&gt;data&lt;&lt;" ";
      	if(curr-&gt;left) q.push(curr-&gt;left);
        if(curr-&gt;right) q.push(curr-&gt;right);
    }
}

}

int main() { /* 1 /
2 3 / \ /
4 5 6 7 / struct Node root = new Node(1); root->left = new Node(2); root->left->left = new Node(4); root->left->right = new Node(5); root->right = new Node(3); root->right->left = new Node(6); root->right->right = new Node(7); bfs(root); return 0; }