title: Why does a queue work for level order traversal of a binary tree?
body: <p><em>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.</em></p>
  
  <p>So I was reading about Level order traversal of binary tree and there exists an <code>O(n)</code> solution when we use a queue data structure.</p>
  
  <p>The algorithm is like this</p>
  
  <blockquote>
    <p>1) Create an empty queue q </p>
    
    <p>2) temp_node = root</p>
    
    <p>3) Loop while temp_node is not NULL</p>
  
  <pre><code>a) print temp_node-&gt;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
  </code></pre>
  </blockquote>
  
  <p>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 !!</p>
  
  <p><a href="https://i.stack.imgur.com/cCydr.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/cCydr.gif" alt="enter image description here"></a></p>
  
  <p>Level order traversal of the above tree is 1 2 3 4 5</p>