Breadth-First Search (Level Order Traversal)

Intro

We use the Breadth-First Search algorithm to traverse the Tree data structures. It is usually used when we want to determine if some value is present in the Binary Tree.

More on Breadth-First Search

Breadth-first search involves searching through a tree one level at a time. We traverse through one entire level of children nodes first, before moving on to traverse through the grandchildren nodes. And we traverse through an entire level of grandchildren nodes before going on to traverse through great-grandchildren nodes. So we traverse the tree level by level. 

In the following Binary Tree, we print the elements level by level:

We first print the root which is on Level 0, then we print the elements of Level 1, then all the elements of Level 2, and Level 3...

So the output after traversing would be: 50, 30, 70, 15, 35, 62, 87, 7, 22, 31



Level Order Traversal of the Binary Trees follows BFS.

In Level Order Traversal (or BFS), we need to keep a reference to all the children nodes of every node that we visit. Otherwise, we’ll never be able to go back to them later and visit them.

To solve this, we can use the Queue data structure.

The really interesting thing about implementing Breadth-first search using a queue is that as we traverse through the subtrees of a binary search tree, each of the nodes that we “check” or “visit” gets added to the queue, so they can be handled later when we starting popping from the queue.

A common term for nodes that we add to our queue is discovered nodes.
A discovered node is one that we add to our queue, whose location we know, but we have yet to actually visit.
In fact, this is exactly what makes a queue the perfect structure for solving the BFS problem.

Implementing the Level Order Traversal of a Binary Tree (or Breadth-First Search)

Below is the implementation of the BFS algorithm in Java.

First, we need to create a Binary Tree.
We'll create a BinaryTree class with a method that creates a simple Tree structure. And we also need a class Node to represent a node in a tree.

class BinaryTree {
  Node root;

  public void createBinaryTree() {
    Node first = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);
    Node fourth = new Node(4);
    Node fifth = new Node(5);
    Node sixth = new Node(6);
    Node seventh = new Node(7);

    root = first;
    first.left = second;
    first.right = third;
    second.left = fourth;
    second.right = fifth;
    third.left = sixth;
    third.right = seventh;
  }

}

class Node {
  Node left;
  Node right;
  int value;

  public Node(int data) {
    this.value = data;
  }
}

With this, we've created a Binary Tree that looks like this:

Now, let's use the Level Order Traversal (BFS) to traverse the Tree and print the elements in Level Order.

We add the following method to the BinaryTree class:

public void levelOrderTraversal() {

  if (root != null) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
      Node current = queue.remove();

      System.out.print(current.value + " ");

      if(current.left != null) {
        queue.add(current.left);
      }

      if(current.right != null) {
        queue.add(current.right);
      }
    }
  }
}

Here, we implemented a Queue data structure using the LinkedList. 
We used a queue to store the elements that we visited, but not ready to be handled (printed).

As you can see, we use the queue, as a memory area, to store the elements that we need to visit again later. And since it is a FIFO (First In First Out), we first store the left node, then the right node, since that is the order we want to pop the elements later as we are iterating.

In the main method, we build the BinaryTree and call the levelOrderTraversal method:

public static void main(String[] args) {
  BinaryTree tree = new BinaryTree();
  tree.createBinaryTree();

  tree.levelOrderTraversal();
}

And we get the output: 1 2 3 4 5 6 7.

And that is what we want. We printed the elements in the correct order - level order.

Breadth-first search (Level Order Traversal) - analysis

BFS has a time complexity of O(n) since we need to visit every node in a Binary Tree.

Space complexity is also O(n) since we are creating a Queue data structure that requires memory space. Queue size would be proportional to number of nodes