Binary Search Tree Vol. 1
Tags: java, beginners, programming, algorithms
Published: 2022-12-31 19:15:33

Source code of the examples [on Github](https://github.com/mcwiise/dev.to/blob/main/binary-tree-ds/src/btree/BinarySearchTree.java)

## What is a Binary Search Tree (BST)?
BST stands for Binary Search Tree; this is a special type of a tree which must be compliant with the following conditions:

- The _**left subtree**_ of the root node must contain values which _**are less than**_ the root node value.
- The _**right subtree**_ of the root node must contain values which _**are greater than**_ the root node value.
- In lights of the above, a BST does not contain duplicate values.
- Every left or right subtree of any node must also be a BST.

![simple bst](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7s9s17a6c6vdg9pjkcec.jpg)

## Searching for a key in a BST
We may guess that searching keys in a binary tree it is just a matter of using one of the traversing algorithms we've seen on this [post]((https://dev.to/mcwiise/binary-tree-data-structure-253b)), but given the fact that a BST is _**a sorted data structure**_, traversing all the nodes searching for a key could represent an unnecessary overhead, thus a better algorithm should look like this:

1. Check if the key to search equals `null` or  the parent node value, then just returns the node.
2. Else, compare the key with the parent node value.
3. So, if the key to search is less than the parent node value, then look for the key in the _**left subtree**_, otherwise look for the key in the **_right subtree._**

```java
public Node search(Node parent, int key){
  if (parent == null || key == parent.value) {
    return parent;
  } else if (key < parent.value){
    return search(parent.left, key);
  } else {
    return search(parent.right, key);
  }
}
```

## Inserting a new key in a BST
As we already understood that keys less than the root node value go to the left subtree and the greater ones to the right, implementing an algorithm to insert keys in a BST should look like this:

1. Check if the parent node is null, then create a new node with the key and just returns it.
2. Else, compare the key with the parent value.
3. So, if the key to insert is less than the parent value, then insert the key in the left subtree, otherwise insert the key in the right subtree.

```java
1.  public static void main(String[] args) {
2.    var bts = new BinarySearchTree();
3.    bts.root = bts.insert(bts.root, 9);
4.    bts.insert(bts.root, 10);
5.    bts.insert(bts.root, 11);
6.  }
7.  public Node insert(Node parent, int key){
8.    if (parent == null){
9.      return new Node(key);
10.   } else if (key < parent.value) {
11.     parent.left = insert(parent.left, key);
12.   } else {
13.     parent.right = insert(parent.right, key);
14.   }
15.   return parent;
16. }
```
Have a look at the `main` method (line 3) where we start the recursive function to insert keys in the tree.

## Deleting a key from a BST
Deleting a key means deleting the node itself. Whenever we need to delete a node from a BST, we have to always make sure that _**none of the 4th conditions of a BST break**_ after deletion, specially the one which says that keys less than the parent value go to the left and the greater ones go the the right, thus we need to analyze the following 3 scenarios to implement a _free bugs_ algorithm:

### Node to be deleted is a **_leaf_**
This is the simplest scenario where the parent node must address to `null` after the child is deleted.

![delete a leave from a BST](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dkeee4eta32ow9tl63k6.jpg)

### Node to be deleted has 1 child
In this case the parent node of the child to delete, must now address to the child's child.

![delete a node with 1 child from BST](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/s2lrjti2p0d3t3vqsy8w.jpg)

### Node to be deleted has 2 children
This is the complex case but it can be solved easily, we just need to replace the node to be deleted by its [inorder predecessor](https://dev.to/mcwiise/binary-tree-data-structure-vol-2-5a52), and why by the inorder predecessor? because this will be _**the largest node of the left subtree**_ after the deletion happens.

![delete a node with 2 child from BST](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/xw0je58t5ah2lcvbn5qk.jpg)

Now, the algorithm:

1. Check the parent, if it is `null` then return it (this is a leaf).
2. Else, if the key to delete is less than parent value then delete the key from the parent left subtree
3. Else, if the key to delete is greater than parent value then delete the key from the parent right subtree.
4. Finally, if the key equals the parent value, it means we have found the node to delete.
5. Find and replace the parent value with its inorder predecessor.
6. Then, delete the predecessor from the parent left subtree.
7. Finally return the parent which will represent the new state of the entire tree after deletion. 

```java
1. public Node delete(Node parent, int key){
2.    if(parent == null){
3.      return parent;
4.    } else if (key < parent.value){
5.      parent.left = this.delete(parent.left, key);
6.    } else if (key > parent.value){
7.      parent.right = this.delete(parent.right, key);
8.    } else {
9.      var predecessor = this.inOrderPredecessor(parent);
10.     parent.value = predecessor.value;
11.     parent.left = this.delete(parent.left, key);
12.   }
13.   return parent;
14. }
```
### Finding the Inorder predecessor of a Node
Lets explore line 9 of the above code snippet where we need to find the Inorder predecessor of the node to delete:

1. The algorithm needs to find the rightmost node of the parent left subtree, since this is the place where we can find _**the largest node of the left subtree.**_

```java
public Node inOrderPredecessor(Node parent) {
  var tempNode = parent.left;
  while(tempNode.right != null){
    tempNode = tempNode.right;
  }
  return tempNode;
}
```