Prerequisites: Binary tree, Queue data structure.
Problem: Given a binary tree, print the level order traversal of its nodes. (i.e., from left to right, on each level).
Solution Approach:
Level order traversal of a binary tree is similar to bread first search traversal. We need a queue data structure
to keep track of all the nodes at a particular level. We start with the root node, push it to the queue.
Then we print/store it and push all its children while popping the root node. In 2nd iteration, the queue is popped till its size which essentially prints nodes at the next level. Simultaneously we keep pushing the children of children and the process goes on like this, until the leaf nodes are printed.
Idea will become more clear once we take a look at the solution.
Time Complexity: O(N), as we need to visit each node once.
Space Complexity: O(N), as we need to store each node in the queue so that later its children can
be visited in level order.