Coding a breadth first traversal is more complex than a depth first traversal (left to right, or right to left.) Although, the code behind the traversal is not much longer or complex, it just requires a bit of thinking. Source code for the breadth first traversal is at the bottom of the post, alongside source code for the more common depth traversal.

I’ve found that there are little examples - online or in books - of how to do a breadth first traversal, especially for Java. I had to teach myself this from a not too friendly C++ example. I’ll try to explain the basic idea of the traversal, before moving on to the code. I hope for your sake that I can actually explain this…

Suppose you have the following tree:

 Now if you were to run a depth traversal you would go in the following order:

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

As the traversal would go to the left most node, then get the root node of that node, then attempt to try this on the right node. As such:

I know, not the greatest of diagrams… that probably just confused you. The red numbers and arrows correspond to the order in which the traversal works. It will go all the way to the left, before going right; this is probably good in the case above, but sometimes you want to get all the values at a certain depth before moving to the next depth (alternatively see this as getting numbers across the breadth of the tree.) For example, if a tutor asked you to get the numbers in order of how close to the root of the tree they were. A normal traversal would not be able to do this, thus you would have to do a breadth first traversal in order to answer the question. Another good example would be searching for a closest ancestor of two people, a basic depth first traversal may get the correct answer on many occasions; however, it would give erroneous answers with more complex trees. If a breadth first traversal was used it would always give the correct answer.

For example, on the tree above a breadth first traversal would give the result:

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

As you can see the numbers are placed in order of their depth, 4 is the root of the whole tree, 2 and 6 are the subnodes of 4. Then finally you get the subnodes of the subnodes (1,3,5, and 7.)

In order to do such a traversal you will need to have two methods and a queue. The first method deals with the root and its subnodes and the second method will deal with all other nodes.

Basically you should dump the subnodes into the queue, then remove one from the queue and repeat the process. The code does a good job in explaining this.

 Now for the code, full source code is available at the bottom of this post.

Basic Traversal

/**
* Simply runs a basic left then right traversal.
*/

public void basicTraversal()
{
//Check if we can go left
if (left != null)
{
left.basicTraversal();
}

//Add the root
list.add(root);

//Check if we can go right
if (right != null)
{
right.basicTraversal();
}
}

Breadth traversal

  /**
* Runs a breadth first traversal
* This method runs once to get the root and it’s subnodes, then runs
* another method to continue the traversal
*
* @param list ArrayList to store the roots in
* @return ArrayList of type Integer
*/
public ArrayList<Integer> getBreadthTraversal(ArrayList<Integer> list)
{

//Add the root to the arraylist, we know it is always the first entry.
list.add(root);

//Basically we add the first set of nodes into the queue for
//traversing.

//Query if left exists
if (left != null)
{
//Then add the node into the tree for traversing later
queue.add(left);
}
//Same for right
if (right != null)
{
queue.add(right);
}

//Then we call the traverse method to do the rest of the work
return traverse(list);
}

/**
* Called by getBreadthTraversal, this should not be ran without it.
*
* This method completes the breadth first traversal. It will remove the
* first Tree from the queue and add their nodes (left and right)
* to the back of the queue. Then it will append the Tree to the
* ArrayList for returning.
*
*
* @param list ArrayList to list tree roots in
* @return list ArrayList
*/
private ArrayList<Integer> traverse(ArrayList<Integer> list)
{
//Keep traversing until we run out of people
while (!queue.isEmpty())
{
/**
* We take one from the queue.
* As a linked list is a queue it operates as “First In First Out”
* also known as FIFO. So if you add something to a queue you have
* to wait until all other objects are removed before you can
* access the object again.
*/
Tree p = queue.remove();

//Check if it has any subnodes
if (p.left != null)
{
//Add the subnode to the back of the queue
queue.add(p.left);
}

//Same for left
if (p.right != null)
{
//Same here, no queue jumping!
queue.add(p.right);
}

//Append to the ArrayList
list.add(p.root);
}

//And return
return list;
}

Tree example source code