There are two main ways of traversing a binary tree: breadth-first and depth-first. With breadth-first traversal, we begin traversing at the top of the tree’s root node, displaying its value and continuing the process with the left child node and the right child node. Descend a level and repeat this step until we finish displaying all the child nodes at the deepest level from left to right.

With depth-first traversal, we always traverse down each left-side branch of a tree fully before proceeding down the right branch. However, there are three traversal options:

*Preorder*is when we perform an action on the current node first, followed by its left child node and its right child node*Inorder*is when we perform an action on the left child node first, followed by the current node and the right child node*Postorder*is when we perform an action on the left child node first, followed by the right child node and then the current node

For this lesson, we will implement the inorder traversal option. The advantage of this option is that the values are displayed in sorted order from the smallest to the largest value.

To illustrate, let’s say we have a binary tree that looks like this:

```
15
/------+-----\
12 20
/ \ / \
10 13 18 22
/ \ / \ / \ / \
8 11 12 14 16 19 21 25
```

We begin by traversing the left subtree at each level, which brings us to the nodes with values `8`

, `10`

, and `11`

. The inorder traversal would be:

`8, 10, 11`

We ascend one level up to visit root node `12`

before we descend back to the bottom where the right subtree of `12`

, `13`

, and `14`

resides.
Inorder traversal then continues with the values:

`12, 12, 13, 14`

We again ascend one level up to visit root node `15`

before we traverse the right subtree starting at the bottom level again. We continue with the bottom leftmost subtree where `16`

, `18`

, and `19`

reside. The inorder traversal continues with:

`15, 16, 18, 19`

We ascend one level up to visit root node `20`

before we descend back to the bottom where the rightmost subtree containing nodes with values `21`

, `22`

, and `25`

resides.

Traversal finishes with:

`20, 21, 22, 25`

The entire inorder traversal becomes:

`8, 10, 11, 12, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 25`

Notice that all the values displayed are sorted in ascending order.

Now let’s implement this inorder traversal for the `BinarySearchTree`

class!

### Instructions

**1.**

Define a method `.depth_first_traversal()`

below `.get_node_by_value()`

. It should have `self`

as the only parameter.

Fill the method body with a `pass`

statement since it is not doing anything yet.

**2.**

Inorder traversal means we will traverse the `left`

child node followed by the root node and the `right`

child node. Remove the `pass`

statement you added in the previous step. Then, inside `.depth_first_traversal()`

:

- Check to see if the left child node exists
- If it does, call this method on the left child node

This traverses the left subtree.

**3.**

Now we want to look at the root node. We can simply print out the depth and the value the root node contains.

After the `if`

statement you just created, and on the same level of indentation as the `if`

statement, add the following print statement which will print the root node’s `depth`

and `value`

:

print(f'Depth={self.depth}, Value={self.value}')

**4.**

The next step would be to traverse the right subtree. Add an `if`

statement, right after the `print()`

statement from the previous step, which will do the following:

- Checks to see if the right child node exists
- If it does, calls this method on the right child node

**5.**

At the bottom of the `BinarySearchTree.py`

file, call the `.depth_first_traversal()`

method on the `BinarySearchTree`

called `tree`

, which has been provided, to print the inorder traversal of the tree.