Breadth-first search implementation

Hello there! If you've somehow stumbled this post, I'm assuming you're trying to understand how the breadth-first search algorithm works, and how to use it to solve problems!

In my other post about the differences between depth-first search and breadth-first search, we talked about cases where we would use the two appropriately. In this post I'll explain how breadth-first search and then implement a way traverse a graph with it.

A major difference between the two is the data structure we use. DFS uses stacks(in case of recursion the call stack) and BFS uses queues.

We'll traverse a tree using BFS and I'll describe each step.

var levelOrder = function(root) {
    // If root is null return an empty array
    if(!root) return []

    const queue = [root] // initialize the queue with root
    const levels = [] // declare output array

    while(queue.length !== 0){
       const queueLength = queue.length // 
       const currLevel = [] // Declare this level

       for(let i = 0; i < queueLength; i++){

           const current = queue.shift()

           if(current.left){
               queue.push(current.left)
           }
           if(current.right){
               queue.push(current.right)
           }

           currLevel.push(current.val)
       }

       levels.push(currLevel)
   }
    return levels
}

We start by checking if root is null. We then initalize our queue and push root into it, since we know that we will visit it first.

Now we go into our while loop, which will keep going until our queue is empty. Then we get the length prior to dequeueing, and loop through to exhaust all options and only to include nodes at currLevel. In our for loop, we add the left and right node for the current level and the push it into currLevel, and after the level is finished we push it into the output array.

This repeats until we get to the last level and eventually the function returns an array of arrays, each one containing the nodes of each level of the tree.