Why does a queue work for level order traversal of a binary tree?

Question

I am not sure if such questions are accepted and I would gladly delete/edit it if they aren't but I think this is not just a discussion question whose answer will depend on opinion and a fact lies behind the solution.

So I was reading about Level order traversal of binary tree and there exists an O(n) solution when we use a queue data structure.

The algorithm is like this

1) Create an empty queue q

2) temp_node = root

3) Loop while temp_node is not NULL

a) print temp_node->data.
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node

I understand the algorithm but what I can't understand is that how would one come up with this solution if he didn't know it before hand. In other words what property of a queue (and may be binary tree) makes it the correct DS to be used in this case. What is the idea behind using a queue here for level order traversal of the binary tree? Thanks !!

Level order traversal of the above tree is 1 2 3 4 5

Answer 1

When you traverse a tree breadth-first, the breadth gets broader and broader. You need a queue to keep track of the roots of subtrees to visit more deeply next, like a "to do" list.

Answer 2

I think if you study BFS more , you will automatically get your answer.

Queue has special property where you can push from one end and pop from another end.
In order they traversed

Like in level order traversal we mark nodes visited and pop them, From other end we push the elements to be mark visited, This is what level order traversal does.

Look at the both operation carefully , Both operations are independent of each other. This isolation of operation is provided by queue.

Answer 3

Generally when we visit a node (say N) during in-order traversal, we push its left child in the queue first and then the right child (given that both exist) and move on to the next element in the queue.

Now this next element will be the right element of previously visited node N.

Basically recursion combined with FIFO property of Queue allows you to do in-order traversal.