Featured Image - "Trees" by RichardBH, used under CC BY 2.0

In the previous article, Depth-First Tree Traversal, I wrote about how to traverse trees with Depth-first approaches;In-Order, Pre-Order, and Post-Order traversals.

In this article, I will talk about the algorithm and an implementation for a breadth-first version.

As a spoiler, you don't have a use a recursion and it needs a familiar data structure.

I am going to use the same tree structure I used in the previous article.

Breadth-first traverse means going through each node from the root of the tree, then next level down and down until you reach the maximum height the tree.

When traversing a tree above, an algorithm needs to go from 4 2 6 1 3 5 7 from top down, left to right;4 is the root, next level down on the left, it's 2, then the node on the same depth, 6, and so on.

As you pass over each level, you need to keep a track of all the nodes sharing the same depth.

From the description, it looks like we need to process whichever node we encountered first in each depth. This is where a queue comes into play.

The algorithm is fairly simple.

Add the root to the queue

While the queue is not empty,

Dequeue a node

Process the node

Queue left node of the node for further processing

Queue right node of the node for further processing

Here is the implementation in C#.

1private static void TraverseBreadthFirst(TreeNode<int> root, List<int> list)2{3if (root == null) return;4
5    Queue<TreeNode<int>> queue = new Queue<TreeNode<int>>();6    queue.Enqueue(root);7
8    while (queue.Count > 0)9    {10        var node = queue.Dequeue();11        list.Add(node.Value);12
13        if (node.Left != null)14            queue.Enqueue(node.Left);15
16        if (node.Right != null)17            queue.Enqueue(node.Right);18    }19}

The implementation follows the algorithm almost word by word except for the simple validation guard clause in the first line.

After the method exits, the list will contain 4 2 6 1 3 5 7.

The working source is available on GitHub.

Conclusion

I've covered bothDepth-first and Breadth-first traversals in two entries.

Breadth-first traversal is less intuitive to implement than depth-first traversals but still easy to do so using a queue abstract data structure.