Breadth First Search in a Binary Tree

When dealing with trees you will find many theories and solutions on how to search a tree. These are general referred to as traversals. The two main types of traversals are Depth First Search and Breadth First Search. Depth First Search variants in type of ways nodes are visited but that is a topic for another day. Today I hope to better my understanding of Breadth First Search using a java example.

Breadth First Search (BFS for short) is also know as a level order traversal. The order in which nodes are visited go from left to right, top to bottom. Meaning the root will start then its left child and then right child. This continues in this pattern all the way to the bottom of the tree.

Time to put this into java. We will start by making a public method and making sure that a tree exists through the root.

public void traverseLevelOrder() {
  if (root == null) {
    return;
  }
}

The reason behind making this a public method is that we can call this on any instance of a tree and get an idea of its depth. We could even customize the method to show the current level with some tweaks.

public void traverseLevelOrder() {
  if (root == null) {
     return;
  }
  Queue<Node> nodes = new LinkedList<>();
  nodes.add(root);
}

We are going to create a queue and then add the root to the queue. The rational for a queue is that using a FIFO (First in First Out) structure we can prioritize left nodes over right and them in order of their level. This will. make so that as long as the queue isn’t empty we will add any left or right children and display the node value.

public void traverseLevelOrder() {
  if (root == null) {
    return; 
  }
  Queue<Node> nodes = new LinkedList<>();
  nodes.add(root);
  while (!nodes.isEmpty()) {
    Node node = nodes.remove();
    System.out.print(" " + node.value);
    if (node.left != null) {
      nodes.add(node.left);
    }
    if (node.right != null) {
      nodes.add(node.right);
    }
  }
}

This is the code of our logic up top. We check for nodes in the queue. If there is we remove the current node saving it for logic. Then we print the removed value. We then check for the existence of left nodes first, then right to add into the queue. This is a simple way to make sure the order will allow the levels to remain in order and go from left to right within the tree at all times.

Breadth First Search is traversal that can give information about depth and levels in a tree with a relativity simple implementation.