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.