Binary Tree Level Order Traversal

Today’s problem will be Binary Tree Level Order Traversal. We will be solving it with two different approaches. First the recursive approach and then we will focus mostly on the iterative approach. Let’s dive in.

The question gives us a binary tree and it is asking us to return an array of arrays, in which each array contains the node values at each level of our input. This seems straight forward. We know how to hit each node in the binary tree with a depth first search function. We will keep track of each level’s values by using a map, having the key be the current depth of the node and the value being an array of those node values which are at that depth. Then we will return the values from the map object.

Next let’s solve this iteratively. First we will initialize a queue and add our root node and the depth level which is 0. We also will initialize an order array that will contain our results. We set a while loop that will run as long as the queue is not empty. First we will shift the first element in the queue and initialize two variables, from this element, the node and the depth. If we encounter a null node we will continue. We will set a while loop that will add an empty array in the order array for each depth level we encounter. Then we add our current nodes value into the corresponding depth array in our order array. Next we add each the left and the right nodes with their corresponding depths to the queue. This continues until the queue is empty and the order array contains our answer.