RUN


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 < size; i++){
        	Node* curr = q.front();
          	q.pop();
          	cout<<curr->data<<" ";
          	if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->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;
}

Report Error/ Suggestion

Related Posts:



CopyRight © 2020

CopyRight © 2020