TEKPOOL

Binary Tree Traversal: Breadth First aka Width First aka Level Order

This is the lesser know of the different kinds of binary tree traversals. Most beginner books and articles only cover the depth first searches. Breadth first traversals are an extremely important tool when working with Binary Trees. The idea is pretty nifty. Basically you work with a Queue, and push the root node into the Queue. Then do the following until you have visited all nodes in the tree.

Visit and Dequeue each element (node) in the queue, and as you visit the node, enqueue it’s left and right child (if present). Continue this until there are no more nodes in the queue. At this point you have finished a breadth order traversal of the binary tree. Let’s work this out with an example.

Here’s a small perfectly balanced tree that I going to be working with. The idea of doing a breadth first traversal is visit the nodes in the following order 1,2,3,4,5,6,7. Initially, you start of with an empty queue and enqueue the root node into the queue. I will display the contents of the queue as we move along.

-------------------------------------------
| 1
--------------------------------------------

Visit each element int the queue, enqueue its left and right nodes and dequeue itself. Once the elements are dequeued, I will put them to the left of the queue.

Visit Node 1, enqueue 2 and 3 and dequeue 1

                              -------------------------------------------
1                             |  2, 3
                              --------------------------------------------

Visit Node 2, enqueue 4 and 5 and dequeue 2

                             -------------------------------------------
1, 2                         |  3, 4, 5
                             --------------------------------------------

Visit Node 3, enqueue 6 and 7 and dequeue 3

                            -------------------------------------------
1, 2, 3                     |  4, 5, 6, 7
                            --------------------------------------------

Visit Node 4, dequeue 4 Nothing to enqueue since 4 has no child nodes

                            -------------------------------------------
1, 2, 3, 4                 |  5, 6, 7
                            --------------------------------------------

Visit Node 5, dequeue 5, Nothing to enqueue since 5 has no child nodes

                          -------------------------------------------
1, 2, 3, 4, 5             | 6, 7
                          --------------------------------------------

Visit Node 6, dequeue 6, Nothing to enqueue since 6 has no child nodes

                        -------------------------------------------
1, 2, 3, 4, 5, 6        |  7
                        --------------------------------------------

Visit Node 7, dequeue 7, Nothing to enqueue since 6 has no child nodes

                         -------------------------------------------
1, 2, 3, 4, 5, 6, 7     |
                         --------------------------------------------

We have just finished a breadth order traversal of a binary tree

Here’s a pseudo-code snippet that of the solution.

BreadthOrderTraversal(BinaryTree binaryTree)
{
        Queue queue;
        queue.Enqueue(binaryTree.Root);
        while(Queue.Size > 0)
        {
                Node n = GetFirstNodeInQueue();
                queue.Enqueue(n.LeftChild); //Enqueue if exists
                queue.Enqueue(n.RightChild); //Enqueue if exists
                queue.Dequeue(); //Visit
         }
}