Question: Binary Tree Level Order Traversal
Output: [[3],[9,20],[15,7]]
As you can see in the above tree, each node of the same level is pushed into a list and all the lists are pushed into a final list.
Solution-1: Using Marker Node
Logic:
Whenever we encounter a Marker node, it indicates that we have reached the end of the level and so we go to the next level.
I'll explain what a marker node is at the end of the article.
Before we go into further steps, we initialize a stack first.
Step-1:
Push the root into the stack, and push a Marker Node M
Step-2:
Pop an element from the stack, insert it into the list, and then push its left and right child into the stack.
If the popped element is M, it indicates we need to begin a new level(i.e initialize a new list) and push M into the stack again.
In this case, 3 is popped and its children 9 and 20 are pushed into the stack. then when we pop again we encounter M, so we push M again into the stack
when we pop again, the element is 9, but 9 doesn't have any non-NULL child, so we don't push anything.
Step-3:
But there is a problem with is approach of inserting marker node into the stack after each level.
The problem is that when we traversed the whole tree(i.e the stack has only one element - Marker node), the
