BFS

Breadth-First Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph level by level.

It starts at a designated vertex (often called the "root" or "source") and systematically explores all the vertices reachable from that vertex.

BFS operates by visiting all the neighbors of a vertex before moving on to the next level of vertices.

Here's how BFS typically works:

1. Start at the source vertex.

2. Visit all the neighbors of the source vertex.

3. Move to the neighbors of these neighbors that have not yet been visited.

4. Continue this process until all vertices reachable from the source vertex have been visited.

BFS is often implemented using a queue data structure.

Here's a high-level outline of the BFS algorithm:

1. Enqueue the source vertex into a queue and mark it as visited.

2. While the queue is not empty: a. Dequeue a vertex from the queue. b. Visit and process the dequeued vertex. c. Enqueue all unvisited neighbors of the dequeued vertex into the queue and mark them as visited.

BFS guarantees that it will visit all vertices in the graph, and it does so in a systematic manner by exploring vertices level by level.

This makes it useful for tasks such as finding the shortest path between two vertices in an unweighted graph, checking if a graph is bipartite, and exploring connected components in a graph.

One thing to note is that BFS requires additional memory to store the visited vertices and the queue.

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.

This is because BFS traverses each vertex and each edge exactly once.

Following this new example image, the values would be traversed in the following order: [10, 6, 15, 3, 8, 20].

Typically, the steps followed by BFS algorithms are the following:

• Create a queue and a variable to store the nodes that have been "visited"

• Place the root node inside the queue

• Keep looping as long as there's anything in the queue

• Dequeue a node from the queue and push the value of the node into the variable that stores the visited nodes

• If there's a left property on the dequeued node, add it to the queue

• If there's a right property on the dequeued node, add it to the queue

pseudocode:

function BFS(root):
    if root is null:
        return an empty list

    create an empty queue
    create an empty list to store the result

    enqueue the root node into the queue

    while the queue is not empty:
        dequeue a node from the queue
        add the value of the dequeued node to the result list

        if the dequeued node has a left child:
            enqueue the left child into the queue
        if the dequeued node has a right child:
            enqueue the right child into the queue

    return the result list

A possible implementation could be the following:

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor() {
        this.root = null;
    }

    insert(value) {
        if (value === undefined) {
            throw new Error("Please provide a valid value for insertion.");
        }

        let newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return this;
        }
        let current = this.root;
        while (true) {
            if (value === current.value) return undefined;
            if (value < current.value) {
                if (current.left === null) {
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if (current.right === null) {
                    current.right = newNode;
                    return this;
                }
                current = current.right;
            }
        }
    }

    BFS() {
        if (!this.root) return [];

        let node = this.root,
            data = [],
            queue = [];
        queue.push(node);

        while (queue.length) {
            node = queue.shift();
            data.push(node.value);
            if (node.left) queue.push(node.left);
            if (node.right) queue.push(node.right);
        }
        return data;
    }
}

// Example usage:
const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);

console.log(tree.BFS()); // [ 10, 6, 15, 3, 8, 20 ]