Binary Tree-Breadth first search explained

In this traversal, we begin at the root node, then move to its left child, visit it, then its right sibling. Traversal then continues to the left child of the root node’s left node then to its right sibling. We then move to the left child of the root’s right child then its right sibling. This process repeats in such fashion, visiting all nodes at each level before moving to the level below until the whole tree is traversed.

Let’s look at an example.

Example 1

With the below tree visit and print each node’s value as its visited.

Output:70 65 82 60 68 80 85 58

Explanation: Traversal begins at the root and node with value 70 is visited and printed. Its left child 65 is visited and printed. Its right sibling 82 is visited and printed. We move to the next level whereby 60,68,80 and 85 are printed in that order. On the last level 58 is printed.

Breadth first search implementation using a queue

The above output is better explained in the below section with help of a diagram.