Data Structure: Breadth First Search(BFS) in JavaScript and TypeScript

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

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

// 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.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));

// 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]);

    });
  });
});