BFS -5 - Medium - Binary Tree Right Side View - Java

Coding Interviews - Binary Tree Right Side View (LeetCode)
This interview question is commonly asked by companies like Meta, Amazon, Snap.
This problem follows the Binary Tree Level Order Traversal pattern. We can follow the same BFS approach and use a queue to efficiently traverse in BFS fashion. The only difference will be that instead of keeping track of all nodes of a level, we will only track the last node of that level and append it to our result List which we return at the end once the while loop is completed.

Link to previous problem
Binary Tree Level order traversal - BFS - https://youtu.be/OlEnmYOEIjM?feature=shared
Binary Tree Level order traversal 2 - BFS - https://youtu.be/QaJ322crQIY?feature=shared
Binary Tree Zigzag Level Order Traversal - BFS 3 - https://youtu.be/zIPTg8hyt04?feature=shared
Binary Tree Average Level order traversal - BFS 4 - https://youtu.be/VTaFLgU1ttk?feature=shared


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-mav...