Binary Search Trees

Table of Contents

What is a Binary Search Tree? #

A Binary Search Tree (BST) is a type of data structure that is used to store data in an organized manner to facilitate fast retrieval, insertion, and deletion operations.

In a binary search tree, each node has at most two children, referred to as the left child and the right child. The key property of a binary search tree is that the value of the

left child is less than the value of the parent node
right child is greater than the value of the parent node.

This means that all nodes to the left of the root node are less than the root node, and all nodes to the right of the root node are greater than the root node. This property holds true for all nodes in the tree, making it easy to search for a specific value in the tree.

      8
      / \
     3   10
    / \    \
   1   6    14
      / \   /
     4   7 13

Searching in a Binary Search Tree #

Searching for a value in a binary search tree is a simple process that takes advantage of the tree’s structure. To search for a value in a binary search tree, you start at the root node and compare the value you are searching for with the value of the current node.

If the value is equal to the current node’s value, you have found the value in the tree.
If the value is less than the current node’s value, you move to the left child of the current node and repeat the process.
If the value is greater than the current node’s value, you move to the right child of the current node and repeat the process.

Flowchart of Searching in a Binary Search Tree #

flowchart TD; A[Start Search] --> B{Is BST empty?} B -->|Yes| N{{Value Not Found}} B -->|No| C{Does value
equal current node?} C -->|Yes| O{{Value Found}} C -->|No| D{Is
value < current node?} D -->|Yes| E[set current node
to left node] E --> G D -->|No| F[set current node
to right node] F --> G{Is node value empty?} G --> |No|C G --> |Yes|H{{Value Not Found}}

Java Implementation of Searching in a Binary Search Tree #

In Java, the search operation in a binary search tree can be implemented using a recursive method that traverses the tree until it finds the value or reaches a leaf node. Here is an example of a search method in a binary search tree:

class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    Node root;

    public Node search(Node node, int value) {
        if (node == null || node.value == value) {
            return node;
        }

        if (value < node.value) {
            return search(node.left, value);
        } else {
            return search(node.right, value);
        }
    }
}

Insertion in a Binary Search Tree #

Inserting a value into a binary search tree is similar to searching for a value. To insert a value into a binary search tree, you start at the root node and compare the value you want to insert with the value of the current node.

If the value is less than the current node’s value and the left child is null, insert the value as the left child of the current node.
If the value is greater than the current node’s value and the right child is null, insert the value as the right child of the current node.
If the value is less than the current node’s value but the left child is not null, move to the left child and repeat the process.
If the value is greater than the current node’s value but the right child is not null, move to the right child and repeat the process.

Flowchart of Insertion in a Binary Search Tree #

flowchart TD; A[Start Insertion] --> B{Is BST Empty?} B -->|Yes| C{{Insert value as root}} B -->|No| D{Compare value
with current node} D -->|Value < Current Node| E[Move to left child] D -->|Value > Current Node| F[Move to right child] E --> G{Is position found?} F --> G G -->|No| D G -->|Yes| H{{Insert value here}}

Java Implementation of Insertion in a Binary Search Tree #

In Java, the insertion operation in a binary search tree can be implemented using a recursive method that traverses the tree to find the correct position to insert the value. Here is an example of an insert method in a binary search tree:

class BinarySearchTree {
    Node root;

    public Node insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.value) {
            node.left = insert(node.left, value);
        } else if (value > node.value) {
            node.right = insert(node.right, value);
        }

        return node;
    }
}

Deletion in a Binary Search Tree #

Deleting a node from a binary search tree is a more complex operation than searching or inserting a node. There are three cases to consider when deleting a node from a binary search tree:

Node to be deleted is a leaf node: If the node to be deleted is a leaf node (i.e., it has no children), you can simply remove the node from the tree.
Node to be deleted has one child: If the node to be deleted has only one child, you can replace the node with its child.
Node to be deleted has two children: If the node to be deleted has two children, you need to find the node with the next highest value (i.e., the smallest value in the right subtree) and replace the node to be deleted with this node. Then, you need to delete the node with the next highest value from the right subtree.

Flowchart of Deletion in a Binary Search Tree #

flowchart TD; A[Start Deletion] --> B{Is BST Empty?} B -->|Yes| C{{Value Not Found}} B -->|No| D{Compare value
with current node} D -->|Value < Current Node| E[Move to left child] D -->|Value > Current Node| F[Move to right child] E --> G{Is value found?} F --> G G -->|No| D G -->|Yes| H{Is node a leaf node?} H -->|Yes| I{{Delete node}} H -->|No| J{Does node have
one child?} J -->|Yes| K{{Replace node with child}} J -->|No| L{{Find next highest value}} L --> M{{Replace node with
next highest value}} M --> N{{Delete next highest value}}

Java Implementation of Deletion in a Binary Search Tree #

In Java, the deletion operation in a binary search tree can be implemented using a recursive method that traverses the tree to find the node to be deleted and handles the three cases mentioned above. Here is an example of a delete method in a binary search tree.

class BinarySearchTree {
    Node root;

    public Node delete(Node node, int value) {
        if (node == null) {
            return node;
        }

        if (value < node.value) {
            node.left = delete(node.left, value);
        } else if (value > node.value) {
            node.right = delete(node.right, value);
        } else {
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            node.value = minValue(node.right);
            node.right = delete(node.right, node.value);
        }

        return node;
    }

    private int minValue(Node node) {
        int minValue = node.value;
        while (node.left != null) {
            minValue = node.left.value;
            node = node.left;
        }
        return minValue;
    }
}

You Might Also Like