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:
        # 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/binary-search-tree-data-structure/
• https://www.javatpoint.com/insertion-in-binary-search-tree