# What Traversal Is Used in Breadth First Search in Tree Data Structure?

//

Heather Bennett

Traversal is a fundamental concept in computer science, especially when it comes to working with tree data structures. One commonly used traversal algorithm is Breadth First Search (BFS). In this article, we will explore the traversal technique utilized in BFS in tree data structures.

Breadth First Search is a graph traversal algorithm that explores all the vertices of a graph or tree in breadth-first order. It starts at the root node and visits all the neighboring nodes before moving on to the next level of nodes. BFS ensures that all nodes at a particular level are visited before moving deeper into the tree.

### The Queue Data Structure

In order to implement BFS, we utilize a queue data structure. A queue follows the principle of First-In-First-Out (FIFO), meaning that elements are added at the end and removed from the front. This allows us to keep track of the nodes we need to visit at each level.

### The Breadth First Search Algorithm

Let’s discuss how BFS works in a tree data structure:

1. Step 1: Enqueue the root node into our queue.
2. Step 2: While the queue is not empty, repeat steps 3-5.
3. Step 3: Dequeue a node from our queue and visit it.
4. Step 4: Enqueue all its children (if any) into our queue.
5. Step 5: Repeat Step 2 until all nodes have been visited.

### An Example

To better understand how BFS traversal works, let’s consider the following tree:

```           A
/   \
B     C
/ \   / \
D   E F   G
```

If we apply BFS to this tree, our traversal order will be: A, B, C, D, E, F, G.

### Visualizing the Traversal Process

Let’s visualize the traversal process using some HTML styling elements:

• Step 1: Enqueue the root node ‘A’ into our queue.
• Step 2: While the queue is not empty:

Queue: [A]

• Step 3: Dequeue ‘A’ from our queue and visit it.

Visited: [A]

• Step 4: Enqueue ‘B’ and ‘C’ into our queue.

Queue: [B, C]

• Step 5: Repeat Step 2 until all nodes have been visited.

Visited: [A], Queue: [B, C]

## The Beauty of Breadth First Search

BFS traversal allows us to explore a tree or graph level by level. This property makes it useful in many applications like finding the shortest path between two nodes or determining if a graph is bipartite. It also helps in solving puzzles like word ladders and maze problems.

## In Conclusion

Breadth First Search is a powerful traversal algorithm used to explore tree and graph data structures. It ensures that all nodes at a particular level are visited before moving on to the deeper levels. By incorporating the queue data structure, BFS provides an efficient way to traverse trees in a breadth-first order.

So, next time you encounter a tree data structure and need to explore it systematically, consider using Breadth First Search for an organized and efficient traversal experience!