When inserting a new value into a Binary Search Tree, we compare it with the root node’s value. We will implement an `.insert()`

method in the `BinarySearchTree`

class, assuming that we call the method from a root node like so:

root_node.insert(new_node)

Here’s how insertion will work:

If a new value is less than the current (root) node’s value, we want to insert it to its left subtree.

- If a left child of the current node doesn’t already exist, we create a new
`BinarySearchTree`

node with that value as this node’s left child. - If a left child already exists, we would call
`.insert()`

recursively on the current node’s left child to insert further down.

If a new value is *not* less than the current (root) node’s value, we’ll want to insert it as a descendant on the right side. The logic for this will be similar:

- If a right child of the current node doesn’t already exist, we create a new
`BinarySearchTree`

node with that value as this node’s right child. - If a right child already exists, we would call
`.insert()`

recursively on the current node’s right child.

The pseudocode for the insertion procedure is as follows:

```
If the new value is less than the root node's value
If a left child node does not exist
Create a new BinarySearchTree with the new value and updated depth and assign it to the left pointer
Else
Recursively call .insert() on the left child node
Else
If a right child node does not exist
Create a new BinarySearchTree with the new value and updated depth and assign it to the right pointer
Else
Recursively call .insert() on the right child node
```

Let’s illustrate the insertion procedure with a tree whose root node has the data `100`

. At each step, an arrow will point at the node being processed.

```
Insert 50
50 < 100, left child node doesn't exist, create a left child node with value 50 and depth 2
==> 100
/
50
Insert 125
125 > 100, right child node doesn't exist, create a right child node with value 125 and depth 2
==> 100
/ \
50 125
Insert 75
75 < 100, left child node with value 50 exists, recursively insert at left child
==> 100
/ \
50 125
75 > 50, right child node doesn't exist, create a right child node with value 75 and depth 3
100
/ \
==> 50 125
\
75
Insert 25
25 < 100, left child node with value 50 exists, recursively insert at left child
==> 100
/ \
50 125
\
75
25 < 50, left child node doesn't exist, create a left child node with value 25 and depth 3
100
/ \
==> 50 125
/ \
25 75
```

Note that we need to update the `depth`

of each inserted node. To do so, we add `1`

to the current node’s depth when we insert a node as a left or right child.

Let’s implement this `.insert()`

method!

### Instructions

**1.**

Define a method, `.insert()`

, with the parameters `self`

and `value`

, below the constructor method.

The method is not doing anything yet, so fill it with a `pass`

statement.

**2.**

We want to know where to place the target value. If the target value is less than the root node’s value, we will need to place it in the `left`

child node. Before doing so, we need to check if the `left`

child node does not exist. If it does not exist, we will add another level to our Binary Search Tree by creating a `left`

`BinarySearchTree`

with the target value and a `depth`

one more than the root node. If the `left`

child node does exist, we will recursively call the `.insert()`

method for the left child node.

Remove the `pass`

statement inside the `.insert()`

method, and write an `if`

statement that checks if the target value is less than the root node’s value. If so, we want to place this on the left side of the tree.

- Nest an
`if`

statement that checks if a`left`

child node does not exist (or is`None`

). If it does not exist, instantiate a`BinarySearchTree`

with the target`value`

and a`depth`

one greater than`self.depth`

, and assign it to`self.left`

. - Right after this
`if`

block, add an`else`

block, also nested in the outer`if`

. This`else`

code executes if a`left`

child already exists. Inside the`else`

, call the`.insert()`

method for the left child node passing the target`value`

as the argument.

**3.**

Alternatively, if the target value is *not* less than the root node’s value, we will place it in the `right`

child node. Before doing so, we need to check if a `right`

child node does not exist. If no `right`

child node exists, we will add another level to our Binary Search Tree by creating a `right`

`BinarySearchTree`

with the target value and a depth one more than the root node. If it does exist, we will call the `.insert()`

method of the right child node.

- Create an
`else`

statement block parallel to the outer`if`

statement from the previous step. - Nest an
`if`

statement that checks if a`right`

child node does not exist. If it does not exist, instantiate a`BinarySearchTree`

with the target`value`

and a new`depth`

and assign it to`self.right`

. - Right after this nested
`if`

, add an`else`

statement such that if`right`

does exist, call its`.insert()`

method passing on`value`

.

**4.**

Let’s add some print statements in `.insert()`

so we can verify the value is added correctly according to the rules of the Binary Search Tree!

Inside `.insert()`

:

Just after you create a new

`BinarySearchTree`

on the left of the node, in the next line paste this print statement:print(f'Tree node {value} added to the left of {self.value} at depth {self.depth + 1}')Just after you create a new

`BinarySearchTree`

on the right, in the next line paste this print statement:print(f'Tree node {value} added to the right of {self.value} at depth {self.depth + 1}')

**5.**

A `BinarySearchTree`

has been created for you with an initial value of `100`

. Insert the following values to the tree in this order:

`50`

`125`

`75`

`25`

At each step, verify the output and make sure the nodes insertion messages match their intended position:

100 / \ 50 125 / \ 25 75