Tree Breadth-first Search: Introduction

About the pattern

A tree is a graph that contains the following properties:

• It is undirectedA graph with edges that do not have a specific direction assigned to them..

• It is acyclicA graph without cycles..

• It is a connected graph where any two vertices are connected by exactly one path.

• Its nodes can contain values of any data type.

The following key features set trees apart from other data structures, such as arrays or linked lists:

• They organize data in a hierarchical manner with a root node at the top and child nodes branching out from it.

• They are nonlinear, which means that the elements in a tree are not arranged sequentially but rather in a branching structure.

• The time complexity for the search and insert operations in trees is typically $O(\log n)$, where $n$ is the number of elements in the tree. In contrast, the time complexity for the search and insert operations in arrays and linked lists can be $O(n)$, where $n$ is the number of elements in the array or list.

• There are multiple ways to traverse them.

A naive approach to exploring the tree would be to revisit already traversed nodes. More specifically, we start at the root node and traverse a particular branch all the way to the leaf node. Then, we start at the root node again and explore another branch. In this way, we’ll revisit many nodes over and over. This would take our time complexity to $O(n^2)$ in the worst case.

Tree breadth-first search (BFS) is another traversal method that explores the tree level by level, starting from the root node. Nodes that are directly connected to the root node by an edge are considered to be at level 1, nodes connected to those at level 1 are at level 2, and so forth.

Here’s an example of the level-by-level representation of nodes in a tree: