Level Order Traversal of Binary Tree in Javascript (Queue)

In my last post I talked about a recursive solution for Leetcode problem 102 Binary Tree Level Order Traversal. Here, I’ll be going through an iterative solution using a queue.

With the recursive solution, we passed a level parameter to our recursive function which we incremented each time we called the function. In this approach we will use a while loop for our queue (while the queue has elements in it, iterate), and within that while loop we will nest a for loop that will process one level of the tree at a time, adding each node in the level to an array, while adding each child of each node to the queue.

Here is the code:

So what is going on in the above?

• First, we check if the input is empty (and return an empty array if it is), and we initialize an empty output variable along with our queue starting with the root node as its first input.
• To process the items in our queue we create a while loop that will continue processing until the queue is empty.
• Within the while loop we get the queue’s length before dequeuing. this will give us the elements at the current level, and will be the condition for our for loop (while i < queueLength). This way we can process the nodes at our current level while adding the children to the queue to be processed with the next iteration of the loop
• Before we begin the for loop for the current level, we also initialize an empty array for the current level being processed. This is the structure into which we will push each node value in the current level and we will then push this current level array into our final output array.
• Now we begin our for loop. Starting our counter at 0, setting the break condition as counter < queueLength, and increment the counter with each call of the loop.
• Within the loop we simply process each node in the queue. First we get the node to be processed by taking the first item in the queue with queue.shift. Next we check if the node has left and right children, and push them onto the queue if it does (you can see for the next iteration of the for loop, these will be the nodes in the next level). After that, we push the current node’s value into our current level array.
• We break out of the for loop once we have processed the current level, and then, still within the initial while loop, we begin the process again with the items currently in the queue, which are the children of the last level of nodes.
• Once our queue is empty, the while loop ends and we return our output array, which now contains all our levels.

Hope this helps!