What is Breadth-First Search (BFS)?

Breadth-First Search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

What data structure is used to implement BFS?

BFS is typically implemented using a queue. The queue is used to keep track of the nodes to visit next. When a node is visited, its neighbors are added to the back of the queue.

Graph Traversal

Breadth-First Search (BFS) Questions

Master BFS for your coding interviews. This guide covers common problems, expert solutions, and AI-powered hints to help you excel in graph and tree traversal questions.

Level Order Traversal of a Binary Tree

A classic application of BFS is the level order traversal of a binary tree. In this traversal, we visit all nodes at a given level before moving to the next level.

                            function levelOrder(root) {
                            if (!root) return [];
                            
                            const result = [];
                            const queue = [root];
                            
                            while (queue.length > 0) {
                            const levelSize = queue.length;
                            const currentLevel = [];
                            
                            for (let i = 0; i < levelSize; i++) {
                            const node = queue.shift();
                            currentLevel.push(node.val);
                            
                            if (node.left) queue.push(node.left);
                            if (node.right) queue.push(node.right);
                            }
                            result.push(currentLevel);
                            }
                            
                            return result;
                            }
                        

AI Coach Hint: The key to BFS is the use of a queue to process nodes in a first-in, first-out (FIFO) manner. This ensures that you explore the graph level by level. Remember to keep track of visited nodes in a graph to avoid infinite loops.