DSA 8# Breadth-first search of a binary tree

Tree representation

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.

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:

Breadth first search result

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

Tree levels

Javascript implementation

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.

final traversal 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.

The Nothing 🔺

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Marius NIEMET

Marius NIEMET

I am just a developer slapping the keyboard daily until magic happens. https://www.mariusniemet.me/