Technical Interview Questions

The largest pool of technical questions with answers, explantions, code and detailed analysis

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

Posted by tekpool on November 4, 2006

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.

BinaryTree                             

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 
         } 
} 

About these ads

11 Responses to “Binary Tree Traversal: Breadth First aka Width First aka Level Order”

  1. Sri said

    Thanks.

  2. John said

    My professor was asking us to show a step by step of this. I knew what a level order traversal was, but I could not figure out how he wanted us to show him. Missed a few classes and started it the last minute. This was a life saver.

  3. uerchelle said

    so how do u actually output the width of the tree, for example the question write a function to find the maximum width of a binary tree

  4. [...] This explanation is excellent. [...]

  5. Nitin said

    Awsome explaination! Thanks.

  6. JustCurious said

    I’m currently working on an assignment that require us
    to construct a binary tree from a given postorder and inorder sequence. I just finished the mechanism, and now I’m trying
    to use level order traversal to print the tree on the screen.
    Though the queue method is rather straight forward, I’m
    wondering if it is possible to travel through a tree without
    the use of a queue(while the tree being a linked list)? I didn’t find anything on the net. Any ideas??

  7. Jose said

    23lruxtTKcZps

  8. Beginner said

    Thanks a lottt!!! I was really struggling for the apropriate explanation of the BFS.

  9. J said

    sei un pezzo di merda come mai non s capisce un cazzo di quello che scrivi forse perchè sei un idiota

  10. thank u. brilliant article

  11. joulu said

    Unioni akatemiarakennushanke pyörätie syöminenhulkkoisoäiti työtehtävä.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 30 other followers

%d bloggers like this: