Summer’s over — what’s your move? Join Pro for 50% off using code [MAKEITHAPPEN](https://www.codecademy.com/checkout?periods=year&plan_id=proGoldAnnualV2&discountCode=MAKEITHAPPEN)


Implement the breadth-first search tree traversal algorithm using Python.

Breadth-First Search: Python

Initializing the search function is the first step to the main algorithm. The parameter of the function should include the following two pieces of data needed to perform the search: 
- the root node of the tree
- the value being searched for

Besides the parameters, the initial function code can take care of the case if the value is not found. To do this, we will write the last line of the function first: `return None`. From the implementation of the previous exercise, we know that when the value `goal_path` is `None` the message `No path found` is output.

Initialize the BFS Function

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.

Breadth-first search tree traversal algorithm.

Introduction

There are many real-world examples that can be represented by the tree data structure. For example, locations on a map can be represented by a tree, where the children of a location node are locations further away. A computer file system is sometimes referred to as a directory tree because directories and files can be represented as nodes. The tree we use in the examples throughout this lesson represents a simple filesystem. 

The tree data structure used in this lesson is implemented in **tree.py**. The only class in this file is called `TreeNode` and can be used to create node objects that link to each other to create a tree. 
```py
class TreeNode:
  def __init__(self, value):
    self.value = value
    self.children = []
```
The class variables that make up the tree are the same ones we’ll need for the algorithm. They are:
- `self.value` is the node value and can be any value capable of being tested with the `==` conditional operator.
- `self.children` is a list of unique `TreeNode` objects. This list is what creates the tree structure that we’ll be working with.

The `TreeNode` class has a `__str__` method that creates a visual representation of the tree structure when a node is printed to the console.

In **main.py**, a sample tree has been created with a root node, `sample_root_node`. This is the tree we will use to test the search implementation.


Values in a Tree

With the function created, we will now start the algorithm by initializing the frontier queue. In this implementation, the frontier queue is called `path_queue` and will hold a list for each node that needs to be searched. These nodes are known as _frontier nodes_. Each list in the queue acts as a path such that the first element of each list will be `root_node` followed by child nodes ending with the frontier node.

We will use the `deque()` python class as the frontier queue. To use `deque` as a queue, we will add elements with the `.appendleft()` method and remove elements with the `.pop()` method. 

The following is an example of `deque()` used as a classic first-in-first-out (FIFO) queue:
```py
from collections import deque

q = deque()
q.appendleft(1) #q = deque([1])
q.appendleft(2) #q = deque([2, 1])
q.appendleft(3) #q = deque([3, 2, 1])
print(len(q)) # outputs 3
q.pop() // #q = deque([3, 2])
q.pop() // #q = deque([3])
q.pop() // #q = deque([])
while q:
  print("In the loop") # No Output
```
In this example:
- The first element added to the queue using `.appendleft()` is `1`.
- The first element removed from the queue using `.pop()` is `1`.
- We used `len()` on a `deque()` object to get the number of elements in `q`.
- A `deque()` object as a `while` condition loops when there are elements in the queue and exits the loop when the queue is empty. 

The Frontier

Congratulations on implementing a breadth-first search algorithm using Python!

Let's go over the steps taken to create a breadth-first search function:
- Before starting the search, define the tree's root node as well as a value to search for.
- Initialize a frontier queue, which holds a path for each node to search
- Loop through the frontier queue to check if the node value matches the value we are searching for.
- Continue the search by adding child nodes to the frontier until the goal has been found, or the tree has been completely searched.


Review

Now on to the second half of the search process: 
```pseudo
For each child of the current node
  Make a copy of the current path
  Add the child to the copy
  Append the updated path to the frontier
```

To ensure each child node has its own list, we need to make a copy of `current_path` and append the child node. Making a copy of the list is important so each child node has its own list added to the frontier. If `current_path` is not copied then the children will be added to the same list which will result in an incorrect path as well as only one child being searched.

Assigning a list to a new variable name does not make a copy of the original list. The new variable will still reference the same list. Python gives us multiple options to make a copy of a list each with its own reference:
```py
original_list = ["My", "ideas", "are", "unique", "!"]
copy_list1 = original_list[:]
copy_list2 = original_list.copy()
copy_list3 = list(original_list)
```
In the above example, the three copied lists can have elements added to them without affecting the original list. 

In the example below we add an element to one of the copies. The output shows the copy is updated and the original list is unchanged.
```py
copy_list1.append("See?")
print(copy_list1)
print(original_list)
# Output
# ["My", "ideas", "are", "unique", "!", "See?"]
# ["My", "ideas", "are", "unique", "!"]
```

Don't Forget the Children

The heart of the algorithm is the loop that contains the search process. The first half of this process is:
```pseudo
Pop the next path list off the frontier
Get the frontier node from the path list
Check if the node value matches the goal value
  If there is a match, return the path to the current node
```

The first iteration of this loop has a frontier with one path: a list with the root node. The node will be retrieved and have its value checked against the goal value. 
