![Breadth First Search(BFS)](https://bigboxcode.com/wp-content/uploads/2024/04/Breadth-First-SearchBFS-1024x450.png)
NOTE
In this article, we are discussing in detail, the implementation of Breadth First Search(BFS) JavaScript and TypeScript.
Step #1: Node Class
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
Step #2: BfsTree Class
class BfsTree {
constructor() {
this.root = null;
}
}
Step #3: Insert Method
class BfsTree {
//...
insert(data) {
const newNode = new Node(data);
if (!this.root) {
this.root = newNode;
return this;
}
let currentNode = this.root;
while (currentNode) {
if (data === currentNode.data) break;
if (data < currentNode.data) {
if (!currentNode.left) {
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
} else {
if (!currentNode.right) {
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
}
}
return this;
}
}
Step #2: bfs Method
class BfsTree {
//...
bfs() {
let data = [];
let queue = [];
let currentNode = this.root;
queue.push(currentNode);
while(queue.length) {
// Dequeue from the queue and get the first item to process
currentNode = queue.shift();
// Add the item to data
data.push(currentNode);
// Enqueue the item which is on the left
if (currentNode.left) {
queue.push(currentNode.left);
}
// Enquey the item which is on the right
if (currentNode.right) {
queue.push(currentNode.right);
}
}
return data;
}
}
Full Source Code
// bfs.js
// Breadth first search implementation in JavaScript
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BfsTree {
constructor() {
this.root = null;
}
insert(data) {
const newNode = new Node(data);
if (!this.root) {
this.root = newNode;
return this;
}
let currentNode = this.root;
while (currentNode) {
if (data === currentNode.data) break;
if (data < currentNode.data) {
if (!currentNode.left) {
currentNode.left = newNode;
break;
}
currentNode = currentNode.left;
} else {
if (!currentNode.right) {
currentNode.right = newNode;
break;
}
currentNode = currentNode.right;
}
}
return this;
}
bfs() {
let data = [];
let queue = [];
let currentNode = this.root;
queue.push(currentNode);
while(queue.length) {
// Dequeue from the queue and get the first item to process
currentNode = queue.shift();
// Add the item to data
data.push(currentNode);
// Enqueue the item which is on the left
if (currentNode.left) {
queue.push(currentNode.left);
}
// Enquey the item which is on the right
if (currentNode.right) {
queue.push(currentNode.right);
}
}
return data;
}
}
export default BfsTree;
Demo
// demo.js
import BfsTree from "./bfs.js";
// Create a new Stack
let bfsTree = new BfsTree();
console.log("----------- BFS example -----------");
// Push items
bfsTree.insert(100);
bfsTree.insert(40);
bfsTree.insert(60);
bfsTree.insert(10);
bfsTree.insert(80);
bfsTree.insert(55);
bfsTree.insert(120);
bfsTree.insert(110);
bfsTree.insert(150);
bfsTree.insert(190);
const bfsResult = bfsTree.bfs();
console.log(bfsResult.map(node => node.data));
Output:
----------- BFS example -----------
[
100, 40, 120, 10,
60, 110, 150, 55,
80, 190
]
Testing
// bfs.test.js
import { describe, it, beforeEach, expect } from "vitest";
import BfsTree from "./bfs";
describe("Breadth First Search", () => {
describe("BFS operation", () => {
let bfsTree;
beforeEach(() => {
bfsTree = new BfsTree();
bfsTree.insert(100);
bfsTree.insert(40);
bfsTree.insert(60);
bfsTree.insert(10);
bfsTree.insert(80);
bfsTree.insert(55);
bfsTree.insert(120);
bfsTree.insert(110);
bfsTree.insert(150);
bfsTree.insert(190);
});
it("Should have correct length", () => {
const bfsResult = bfsTree.bfs();
expect(bfsResult.length).toBe(10);
});
it("Should traverse in right order", () => {
const bfsResult = bfsTree.bfs();
const bfsData = bfsResult.map(node => node.data);
expect(bfsData).toMatchObject([100, 40, 120, 10, 60, 110, 150, 55, 80, 190]);
});
});
});
Time Complexity
Operation | Complexity |
---|---|
Insert | |
Search |
Source Code
Use the following links to get the source code used in this article-
Source Code of | Implementation Code | Demo Code | Test Code |
---|---|---|---|
JavaScript Implementation | ![]() | ![]() | ![]() |
TypeScript Implementation | ![]() | ![]() | ![]() |
Related Data Structures
Command | Details |
---|---|
Singly Linked List | ![]() |
Other Code Implementations
Use the following links to check the BFS implementation in other programming languages-