Identify

when dealing with the problems involving traversal of a tree in a level-by-level order

Motive

traverse a tree and use a queue to keep track of all the nodes of a level before jumping onto the next level
works by pushing the root node to the queue and then continually iterating until the queue is empty, for each iteration, we remove the node at the head of the queue and “visit” that node
after removing each node from the queue, we also insert all of its children into the queue

we will use a Queue to keep track of all the nodes of a level before we jump onto the next level
this also means that the space complexity of the algorithm will be O(N), where N is the maximum number of nodes on any level
we can use a Queue to efficiently traverse in BFS fashion. Here are the steps of our algorithm:
1. start by pushing the root node to the queue
2. keep iterating until the queue is empty
3. in each iteration, first count the elements in the queue (let’s call it level_size). We will have these many nodes in the current level
4. next, remove level_size nodes from the queue and push their value in an array to represent the current level
5. after removing each node from the queue, insert both of its children into the queue
6. if the queue is not empty, repeat from step 3 for the next level