Insertion and search in binary search tree
Tags: algorithms, beginners, codenewbie, computerscience
Published: 2021-06-28 23:43:41

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

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

```python
    # 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*)

## References and useful resources

+ [https://www.geeksforgeeks.org/insert-a-node-in-binary-search-tree-iteratively/](https://www.geeksforgeeks.org/insert-a-node-in-binary-search-tree-iteratively/)
+ [https://www.geeksforgeeks.org/binary-search-tree-data-structure/](https://www.geeksforgeeks.org/binary-search-tree-data-structure/)
+ [https://www.javatpoint.com/insertion-in-binary-search-tree](https://www.javatpoint.com/insertion-in-binary-search-tree)