🌲 🌳 Binary Search Tree 🌲🌳

Why do we need Binary Search trees?

Binary Search Trees are effective solutions to any real word problems and they are optimum solutions due to speed and accuracy.
Binary Search Tree is O (log n) average case.
Binary Search Tree is like a branch-like format, the algorithm knows where to search for the elements.
There are fewer comparisons done to find key-value pairs.
It is O (log n).
It supports operations like search inserts and deletes. For example, if you are trying to design an account class you may have the account number for the clients stored in a Binary Search Tree, and through this system it can support operations like inserting that is opening an account, searching for an account, or deleting an account.

Properties of Binary Search Tree:

There is the main node or top-level node: It has a left and right subtree.
Left value Subtree has values less than node.
Right Side Subtree has values greater than the node.

Binary Search Tree Searching: (PseudoCode)
1- Check if the Binary Search Tree is empty, if yes print a not found message, meaning it is not there.
2- If it is not empty, compare the key with the given value.
3- If root equals given value, then print key found.
4- It is not equal to the given value check where to search

if given value < root key search left subtree, then start from step 1 again till you find it.
- If the given value is > root key, search the right subtree then start from step 1 again till you find it.

*Binary Search Insertion *
1- Check if the Binary Search Tree is empty if yes insert the node.
2- If it is not empty compare the root with the given value
3- If root key < given value go to the right subtree to find a position to insert the new node.
4- If root key > given value go to the left subtree to find a position to insert the new node.

Binary Search Removal:
There are 3 cases to remove:

- Empty Tree:
You can't do anything since there is nothing to remove.

Do Nothing

- Root Node
Find the Smallest item on left and delete the root node and replace it with the smallest item on left

             10                              11
           /     \         delete(10)      /     \
          7       15       --------->    7        15 
         /  \    /  \                   /  \        \ 
        5    8  11   18                5    8        18

- All Other Case is divided into 3 types:

Deleting Leaf Node that has no children : Simply delete the leaf node without any issues.


             10                             10
           /     \         delete(5)      /     \
          7       15       --------->    7       15 
         /  \    /  \                     \     /  \ 
        5    8  11   18                    8   11   18

Deleting Node that has one child: Delete the node and replace deleted node with its child.

             10                              10
           /     \         delete(15)      /     \
          7       15       --------->    7       11 
         /  \    /                      /  \      
        5    8  11                     5    8

Deleting Node that has 2 children Either go to the right tree and find the smallest value/ go to the left tree and find the biggest value to push it up in the node.

             10                             10
           /     \         delete(15)      /     \
          7       15       --------->    7       11 
         /  \    /  \                   / \        \ 
        5    8  11   18                5   8      18

Pre Order Traversal