BFS 2 - Easy - Binary Search Level Order Traversal 2 - Java смотреть онлайн

Coding Interviews - Binary Search Level Order Traversal 2 (LeetCode)
This interview question is commonly asked by companies like Facebook, Amazon, Google.
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 levelSize). We will have these many nodes in the current level.
4.Next, remove levelSize 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.

Link to previous problem
Binary Tree Level order traversal - BFS - https://youtu.be/OlEnmYOEIjM

In this problem, we will use a LinkedList instead of an ArrayList for our result list. As in the case of ArrayList, appending an element at the beginning means shifting all the existing elements. Since we need to append the level array at the beginning of the result list, a LinkedList will be better, as this shifting of elements is not required in a LinkedList.

Time Complexity -
The time complexity of the above algorithm is O(N), where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity -
The space complexity of the above algorithm will be O(N) as we need to return a list containing the level order traversal. We will also need O(N) space for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need O(N) space to store them in the queue.

Know more about me
LinkedIn - https://www.linkedin.com/in/umang-mavani/