Breadth first walking of a binary tree

While not rocket science, breadth-first walking of a binary tree is not intuitive at all. Most people need depth-first tree walking and that is often done with recursion or by using a local stack implementation. This is because you work from the top of the tree down to the bottom and then back up zip-zagging through the nodes, and pushing nodes onto the stack as you go. Breadth-first walking is a lot different because you are essentially walking the tree from left to right, then down to the next level. Typically, you are simply outputting the contents of the tree, but this does have other uses too.

Just the basics
Let's specify a simply set of requirements and see how we met those for outputting a binary tree in breadth-first order.

• It must output the contents of each node in breadth-first order.

Well, that's fairly easy. By walking the tree using a queue, instead of a stack, we can easily solve this problem. The first thing we setup is the push into the queue. This is often called enqueue but in my version of stl, it's push. We ignore the fact that if someone passes us a NULL head, we'll crash since that is a dummy mistake but you can add an assert if you find it necessary. This will be our first node that we'll print. Before printing, we'll add the left and right nodes to the queue.

Now here is the confusing part for me: how does it walk the tree just by sticking nodes into the queue? Well, here's how. Let's start with this tree. This is a balanced tree, but this algorithm works for all binary trees.

So in the code, first we push the top-most node, 0, into the queue. Then we pop it off to work with it. From 0, we grab it's left node, 1, and push that into the queue, then we push 2. Now the queue only contains 1 and 2. We print the contents of 0, then move to the next node. Then 1 is popped off of the top, and it's children are added. Then we print the contents of 1, and then move to the next node... 2. Rinse and repeat.

void PrintTreeDepthFirstStacked2 (BNode* head)
{
queue ; Queue ;
Queue.push (head);

 while (Queue.empty () == false)
 {
     BNode* currentnode = Queue.front ();
     Queue.pop ();

     if (currentnode->left)
     {
         Queue.push (currentnode->left);
     }
     if (currentnode->right)
     {
         Queue.push (currentnode->right);
     }

     cout << currentnode->Value << ",";
 }
 cout << endl;
}

A little more advanced
Nothing fancy, but let's add another requirement.

• Print a new line at the end of every level in the tree.

So this means that we need to detect the end of a line and then output a newline. How do you know when you've reached the end of a level? We can't just rely on the left and right because if we do that, we'll have a lot of false-positives. Let's look at an example: if we start from node 1 and we add left-right and output a newline, we'll we putting out a newline after 3 and 4 which doesn't suit our requirements. What we need is a sentinel or NULL node.

This is how it works. First we shove a NULL node into the queue after our head. Then everytime we run into a sentinel, we push another sentinel into the tree. Let's work this out. After the first node, 0, we detect a sentinel. We do need to be sure that we don't repeat adding sentinels forever, so we perform a simple test at the end of the queue. If we aren't at the end, we add a sentinel node. Later in the code, we output a newline if the sentinel was detected. Let's walk this a bit and see what happens.

From 0, we output it and move to the next node. It is a sentinel, so we add another sentinel which will come after the children nodes 1 and 2. Out current queue contents are: 1, 2, sentinel. Now we print a newline, and then move onto the children of 0. 1 comes around and we add it's children and we loop to 2, add it's children. In the next loop, we have the sentinel. This means that we add another sentinel, and print a newline. The sentinels are signals for more sentinels until we come to an empty queue. Look at how clean and simple the code can be.

void PrintTreeDepthFirstStacked (BNode* head)
{
   queue <BNode*> Queue ;
   BNode* sentinel = NULL;

   Queue.push (head);
   Queue.push (sentinel);

   while (Queue.empty () == false)
   {
       BNode* currentnode = Queue.front ();
       Queue.pop ();

       if (currentnode == sentinel)
       {
           if (Queue.empty () == false) // when we get to te end,
                               // we don't want an infinite repeating queue
           {
               Queue.push (sentinel);
           }
       }
       else
       {
           if (currentnode->left)
           {
               Queue.push (currentnode->left);
           }
           if (currentnode->right)
           {
               Queue.push (currentnode->right);
           }
       }
       if (currentnode == sentinel)
       {
           cout << endl;
       }
       else
       {
           cout << currentnode->Value << ",";
       }
    }
}