hi, this is part 4 of the tree data structure we'll explain binary search tree operations with their implementation such as insertion, and search.

In the next post, we will talk about the deletion.

#day_16

## Insertion in the binary search tree

- Let's say we want to insert 17 in this binary search tree.

```
20
/ \
12 23
/ \ / \
7 15 21 35
```

- Since 17 < 20, we will go to the left sub-tree.
- 17 > 12, we will go the right.
- 17 > 15 and the no more child in the right's why we will go to the right and insert it. so this binary search tree above will be like this:

```
20
/ \
12 23
/ \ / \
7 15 21 35
\
17
```

### The insert approach

- We need to know that the inserted node will be always one of the binary search tree leaves.
- while the root is None(
*null*) store the previous root in a variable- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
`root = root. right`

- else (
*that means the previousRoot is greater than or equal the elementToInsert*) move to the root of the left sub-tree`root = root. left`

- if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree
- When the loop break (
*stop*), the previous root will be:- case 1:
`previousRoot = None`

if the binary search tree is empty. so the previousRoot will be the new Node`previousRoot = Node(elementToInsert)`

- case 2:
`previousRoot < elementToInsert`

if the previousRoot is less than the elementToInsert, so the node will be the right child of the previousRoot`previousRoot.right = elementToInsert`

- case 3:
`previousRoot >= elementToInsert`

if the previousRoot is greater than or equal the elementToInsert, so the node will be the left child of the previousRoot`previousRoot.left = elementToInsert`

- case 1:

### Implementation of insert using python

```
def insert(elementToInsert: int, root = None):
# new node
TheNewNode = Node(elementToInsert)
previousRoot = None
while root is not None:
previousRoot = root
# if the root's value is less than elementToInsert
if root.value < elementToInsert:
# the root variable will be the root of the right sub-tree
root = root.right
# if the root value is greater than or equal elementToInsert
else:
# the root variable will be the root of the left sub-tree
root = root.left
# if the binary search tree is empty
if previousRoot is None:
previousRoot = TheNewNode
# if the previous root value is greater than or equal the elementToInsert
elif previousRoot.value >= elementToInsert:
# the new node will be its left child
previousRoot.left = TheNewNode
# if the previous root value is less than the elementToInsert
else:
# the new node will be its right child
previousRoot.right = TheNewNode
return TheNewNode
```

## Search in the binary search tree

We want to search for example the number 21

```
20
/ \
12 23
/ \ / \
7 15 21 35
```

- start from the root and compare its value with the wanted number (20 < 21), so we will go to the right sub-tree and compare its root with the wanted element.
- (23 > 21), that's why we will go to the left sub-tree and compare its root with the wanted element.
- since (21 == 21), will return the node

### the search approach

- compare the root value with the wanted element.
- If the root is None (null)
*that means the element is not found*return False. - Else If the root is equal to the wanted element return the root.
- Else If the root is greater than it, return the same function with these arguments:(root of the left sub-tree, wanted element)
- Else (that means the root is less than the wanted element) return the same function with these arguments:(root of the right sub-tree, wanted element)

- If the root is None (null)

### implementation of the search algorithm in the binary search tree

```
# If there are no more nodes.
# that means the node value will be None(null)
# that means the wanted element doesn't exist
if root == None:
# the wanted element is not found so return False
return False
# if the root value is equal to the wanted element
# that means the wanted element is found
if root.value == wantedElement:
# return the node
return root
# if the root value is smaller than the wanted element
if root.value < wantedElement:
# return the same function with the root of the right sub-tree
return search( wantedElement, root.right)
# if the root value is greater than or equal the wanted element
if root.value >= wantedElement:
# return the same function with the root of the left sub-tree
return search( wantedElement, root.left)
```

Happy coding! see you next post (*we will discuss deletion*)

## Top comments (0)