Implementing a Binary Search Tree

Introduction

In this lab, we will learn how to implement a Binary Search Tree in Java. A Binary Search Tree is a binary tree data structure in which the value of each node is greater than or equal to the values in its left subtree and less than or equal to the values in its right subtree.

Skills Graph

Creating the BSTNode Class

Firstly, let's create a Java class representing the node of a binary search tree and call it BSTNode. A node in a binary search tree should have a value and two child nodes - one to its left and one to its right.

class BSTNode {
    int value;
    BSTNode leftChild;
    BSTNode rightChild;

    BSTNode(int val) {
        this.value = val;
        this.leftChild = null;
        this.rightChild = null;
    }
}

Inserting Elements into the Binary Search Tree

To insert elements into the binary search tree, we follow the following algorithm:

• If the new value is less than the current node value, then recurse to the left child.
• If the new value is greater than the current node value, then recurse to its right child.
• If the current node is null, then add the new value at this position.

public static BSTNode insert(int value, BSTNode current) {
    if (current == null) {
        BSTNode newNode = new BSTNode(value);
        return newNode;
    } else {
        if (value < current.value)
            current.leftChild = insert(value, current.leftChild);
        else
            current.rightChild = insert(value, current.rightChild);
    }
    return current;
}

To test this method, create the binary search tree and insert some elements:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Print out the tree to verify the insertion
    System.out.println("Traversal after insertion: ");
    inorderTraversal(root);
}

// Function to traverse the tree inorder
public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

Output:

Traversal after insertion:
5 7 9 12 20 21

Searching for an Element in the Binary Search Tree

To search for an element in the binary search tree, we follow the following algorithm:

• If the current node's value matches the value that we are trying to find, then return true.
• If the current node's value is greater than the value that we are trying to find, then recurse to the left child.
• If the current node's value is smaller than the value that we are trying to find, then recurse to the right child.
• If the current node is null then return false.

public static boolean search(int key, BSTNode current) {
    if (current == null)
        return false;
    if (current.value == key)
        return true;
    else {
        if (key < current.value)
            return search(key, current.leftChild);
        else
            return search(key, current.rightChild);
    }
}

To test this method, search for some elements:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Search for elements
    System.out.println(search(7, root));
    System.out.println(search(9, root));
    System.out.println(search(17, root));
}

Output:

true
true
false

Deleting an Element from a Binary Search Tree

Deleting an element from a binary search tree is a bit more complex than the previous steps since we need to handle different cases depending on the type of node:

• If the node has no children (a leaf node), simply remove it.
• If the node has only one child, replace it with its only child.
• If the node has two children, replace it with the minimum value from the right subtree or the maximum value from the left subtree.

public static BSTNode delete(int value, BSTNode current) {
    if (current == null)
        return current;
    if (value < current.value)
        current.leftChild = delete(value, current.leftChild);
    else if (value > current.value)
        current.rightChild = delete(value, current.rightChild);
    else if (value == current.value) {
        if (current.leftChild != null && current.rightChild != null) {
            int min = current.rightChild.value;
            BSTNode temp = current.rightChild;
            while (temp.leftChild != null) {
                min = temp.leftChild.value;
                temp = temp.leftChild;
            }
            current.value = min;
            current.rightChild = delete(min, current.rightChild);
        } else if (current.leftChild == null)
            return current.rightChild;
        else if (current.rightChild == null)
            return current.leftChild;
    }
    return current;
}

To test this method, delete some nodes and print the tree:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    // Delete some nodes
    root = delete(12, root);
    root = delete(20, root);
    root = delete(9, root);

    // Print the tree to verify the deletion
    System.out.println("Traversal after deletion: ");
    inorderTraversal(root);
}

Output:

Traversal after deletion:
5 7 21

Traversing the Binary Search Tree

We can traverse a binary search tree in different ways:

• Inorder Traversal (Left-Root-Right)
• Preorder Traversal (Root-Left-Right)
• Postorder Traversal (Left-Right-Root)
• Level-order Traversal (BFS)

public static void inorderTraversal(BSTNode current) {
    if (current == null)
        return;
    inorderTraversal(current.leftChild);
    System.out.print(current.value + " ");
    inorderTraversal(current.rightChild);
}

public static void preorderTraversal(BSTNode current) {
    if (current == null)
        return;
    System.out.print(current.value + " ");
    preorderTraversal(current.leftChild);
    preorderTraversal(current.rightChild);
}

public static void postorderTraversal(BSTNode current) {
    if (current == null)
        return;
    postorderTraversal(current.leftChild);
    postorderTraversal(current.rightChild);
    System.out.print(current.value + " ");
}

public static void levelOrderTraversal(BSTNode root) {
    Queue<BSTNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        BSTNode temp = queue.poll();
        System.out.print(temp.value + " ");
        if (temp.leftChild != null)
            queue.add(temp.leftChild);
        if (temp.rightChild != null)
            queue.add(temp.rightChild);
    }
}

To test these methods, print the tree using each traversal technique:

public static void main(String[] args) {
    BSTNode root = new BSTNode(12);
    root = insert(7, root);
    root = insert(20, root);
    root = insert(5, root);
    root = insert(9, root);
    root = insert(21, root);

    System.out.print("Inorder Traversal: ");
    inorderTraversal(root);
    System.out.print("\nPreorder Traversal: ");
    preorderTraversal(root);
    System.out.print("\nPostorder Traversal: ");
    postorderTraversal(root);
    System.out.print("\nLevel-order Traversal: ");
    levelOrderTraversal(root);
}

Output:

Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21

Summary

In this lab, we have learned how to create, insert elements into, search for an element in, delete an element from, and traverse a Binary Search Tree in Java.

We first created the BSTNode class which represents a node in the binary search tree. We then implemented the insertion, search, and deletion functionalities using algorithms specific to binary search trees. Finally, we learned how to traverse the binary search tree using different traversal techniques such as inorder, preorder, postorder, and level-order traversal.

With these concepts, you should be able to implement binary search trees in your own Java programs.