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.