Breadth First Search (for binary trees)

gistfile1.txt

Note: This example is for a binary tree but for graphs, you do a similar thing but need to keep track of which nodes you have visited (until you visit all of them) and also add all children to the queue, not just the left and right child. 

Tree:
      5
    /  \
   2      6
  / \    / \
 1   3   4  7
 
 Add the root to the BFSArray (the results). Add its children to the queue.
 Then, while the queue is not empty, dequeue from the queue. Add that element to the BFSArray and its children (if any) to the Queue.
 Continue until the queue is empty.
 BFSArray: [5]   Queue: [ 2, 6] (add root to the results and its chidren-2 and 6- to the queue)
 BFSArray: [5,2]   Queue: [6, 1, 3] (dequeue 2 and add it to the results; add its children-1 and 3- to the queue)
 BFSArray: [5,2,6]   Queue: [1, 3, 4, 7] (dequeue 6 and add it to the results; add its children- 4 and 7 to the queue)
 BFSArray: [5,2,6,1]   Queue: [3, 4, 7] (dequeue 1 and add it to the results; it does not have any children so don't add to the queue)
 BFSArray: [5,2,6,1,3]   Queue: [4, 7] (dequeue 3 and add it to the results; it does not have any children so don't add to the queue)
 BFSArray: [5,2,6,1,3,4]   Queue: [7] (dequeue 4 and add it to the results; it does not have any children so don't add to the queue)
 BFSArray: [5,2,6,1,3,4,7]   Queue: [ ] (dequeue 7 and add it to the results; it does not have any children so don't add to the queue)
 Now the queue is empty so stuff. BFSArray contiains the results of Breadth First Search.