Learn

The breadth-first search is a tree traversal algorithm that searches a tree level by level. The search starts with the root node and works its way through every sibling node on a level before moving deeper into the tree. There are multiple ways to implement a breadth-first search. In this lesson, we will use an iterative approach that involves maintaining a collection of nodes in a *frontier queue*.

Here are the steps needed to implement this search algorithm:

- Import values into a tree data structure
- Determine the root node of the tree and the goal value to search for
- Create a queue of node paths that lead to the nodes that need to be searched
- Get a path from the queue to obtain the next node to search
- If the goal value isn’t found in the node, add a path to the queue for each of the node’s children

The iterative approach to the breadth-first search algorithm is also represented by the flow diagram next to the code editor. In this lesson, we’ll learn how to implement this algorithm in Python.

### Instructions

**1.**

Run the code in the editor to see the breadth-first search in action.

# Sign up to start coding

By signing up for Codecademy, you agree to Codecademy's Terms of Service & Privacy Policy.