## DEV Community

Aya Bouchiha

Posted on • Updated on

# Insertion and search in binary search tree

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
``````
1. Since 17 < 20, we will go to the left sub-tree.
2. 17 > 12, we will go the right.
3. 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

1. We need to know that the inserted node will be always one of the binary search tree leaves.
2. while the root is None(null) store the previous root in a variable
1. if the previousRoot is less than the elementToInsert moves to the root of the right sub-tree `root = root. right`
2. else (that means the previousRoot is greater than or equal the elementToInsert) move to the root of the left sub-tree `root = root. left`
3. When the loop break (stop), the previous root will be:
1. case 1: `previousRoot = None` if the binary search tree is empty. so the previousRoot will be the new Node `previousRoot = Node(elementToInsert)`
2. 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`
3. 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`

### 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
``````
1. 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.
2. (23 > 21), that's why we will go to the left sub-tree and compare its root with the wanted element.
3. 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)

### 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:
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)