Binary Search Tree Vol. 1

Source code of the examples on Github

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.

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, 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.

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.

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.

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.

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, and why by the inorder predecessor? because this will be the largest node of the left subtree after the deletion happens.

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.

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.

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