🌲 🌳 Binary Search Tree 🌲🌳
Published: 2022-12-16 15:47:49

**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:**

1. There is the main node or top-level node: It has a left and right subtree.
2. Left value Subtree has values less than node.
3. 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.

{% embed https://www.youtube.com/watch?v=F8WLu--EhYU %}

**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:**

1. 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
```
2. 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
```

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lbf9e72df2apljh4os7f.png)
**Pre Order Traversal**
{% embed https://www.youtube.com/watch?v=U99TAMyQU-E %}

**In Order Traversal**
{% embed https://www.youtube.com/watch?v=hIgwX6OG5P0 %}

**Post Order Traversal**
{% embed https://www.youtube.com/watch?v=rA_f8GenBtw %}