Breadth-first search of a binary tree

In this previous blog post we learned what a binary tree is, how it can be represented, and the different types of binary trees, in conclusion, we've said that a binary tree, unlike other data structures, can be browsed in two different ways breath-first search and depth-first search.
This post will be focused on breath-first search.

This post will be focused on breath-first search.

What's breadth-first search Tree traversal ?

Breath-first search is an algorithm that allows you to traverse a Tree level by level that's why it's also called Level Order Traversal. The principle is to display all nodes at the same level before moving to the next level. Basically, if you traverse the Tree above by following the Level order traversal your result should be:

As you can see the order follows the tree's levels

Javascript implementation

function bfs(root){
  const queue = [root]
  const result = []; 
  let current; 

  while(queue.length){
    current = queue.shift(); 
    result.push(current.val);

    if(current.left) queue.push(current.left);
    if(current.right) queue.push(current.right);
  }

  return result;
}

explanation

The Level order traversal is implemented by using a queue. A queue is a basic data structure that follows the FIFO (First in First out) principle.

The function receives one parameter which is the Tree root. We init the queue with the Tree root, we declare an empty array that will contain the result of our traversal and a variable called current.

While the queue isn’t empty that means there are nodes to traverse. Inside the loop, we get a node in the queue that become current, since the queue follows the FIFO principle it will be the first node in the queue. We push the value inside the current into the result table and we check if the current has children, if so we push them into the queue.

Since the queue follows the FIFO principle, the nodes at the same level will be pushed into the result array before moving to the next level.

Illustration

For the illustration we gonna traverse the binary tree below:

First, we have to init the queue with the root node and init the result with an empty array.

During the first lap into the loop, the root node will be removed from the queue, its value will be pushed into the result and its children push into the queue.

Since the queue follows the FIFO (first in first out) the next node that will be removed from the array is 14. Then its value will be added to the result array and its children will also be added to the queue.

In his turn, 35 will be removed from the queue, its value will be added to the result, and its children in the queue.

Finally, since the nodes that are left in the queue are leaves(nodes without children) they will be added one by one to the result.

Complexity analysis

The Level Order traversal has a time complexity of O(n) since we traverse the entire Tree only once and space complexity of O(n) because we use a queue to store nodes during the traversal.

Conclusion

We are at the end of our post. Hope we learn something new by reading this one.