Learn

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.

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.

Instructions

In main.py, print the defined root node, sample_root_node, to take a look at the tree structure.

Under the print() statement, define a variable goal_path and assign it the value, None.

This variable will be used to hold the return value of the breadth-first search.

Now test goal_path to check if it is empty:

Create an if statement with the condition goal_path is None.
Inside the if body, print No path found.
Add an else statement and inside that body, print Path found.

Now print the path elements:

Inside the else body, create a for loop with a loop variable node and iterates through goal_path
Inside the for loop body, print node.value

Sign up to start coding

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

Or sign up using:

Already have an account?