Learn

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``````