Binary Search Tree Overview

A Binary Search Tree (BST) is a binary tree where each node contains a key and a value. For any given node, the keys of all nodes in its left subtree are smaller than the key of that node, while the keys of all nodes in its right subtree are greater than the key of that node.

The main characteristic of a Binary Search Tree is that it supports efficient search, insertion, and deletion operations. Since an in-order traversal of a Binary Search Tree yields a sorted sequence, it facilitates range queries and sorting operations.

Below are some basic properties of a Binary Search Tree:

1. For any given node, the keys of all nodes in its left subtree are smaller than the key of that node, while the keys of all nodes in its right subtree are greater than the key of that node.
2. For any given node, both its left and right subtrees are Binary Search Trees.
3. For any given node, the maximum key in its left subtree is smaller than the key of that node, and the minimum key in its right subtree is greater than the key of that node.
4. For any given node, the difference in height between its left and right subtrees does not exceed 1.

The time complexity of search, insertion, and deletion operations in a Binary Search Tree depends on the height of the tree. Therefore, to ensure the balance of a Binary Search Tree, balanced binary trees (such as AVL Trees or Red-Black Trees) can be used instead.

Code Implementation

::: code-tabs
@tab Java

class binarySearchTree {
    class Node{
      private int data;
      Node leftChild;
      Node rightChild;
      Node(int value){
        this.data = value;
        leftChild = null;
        rightChild = null;
      }
      public Node getLeftChild(){ return leftChild; }
      public Node getRightChild(){ return rightChild; }
      public int getData(){ return data; }
      public void setData(int value) { this.data = value; }
      public void setLeftChild(Node left){ this.leftChild = left; }
      public void setRightChild(Node right){ this.rightChild = right; }
    }
    private Node root;
    public Node getRoot() {
        return root;
    }
  
      public void setRoot(Node root) {
        this.root = root;
    }
    boolean delete(int value, Node currentNode) {
        if (root == null) {
            return false;
        } 
        Node parent = null; 
        while(currentNode != null && (currentNode.getData() != value)) {
            parent = currentNode;
            if (currentNode.getData() > value)
                currentNode = currentNode.getLeftChild();
            else
                currentNode = currentNode.getRightChild();
        }
        if(currentNode == null) {
            return false;
        }
        else if(currentNode.getLeftChild() == null && currentNode.getRightChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(null);
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
                parent.setLeftChild(null);
                return true;
             }
            else{
                parent.setRightChild(null);
                return true;
            }
        } else if(currentNode.getRightChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(currentNode.getLeftChild());
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
                parent.setLeftChild(currentNode.getLeftChild());
                return true;
            }
            else{
                parent.setRightChild(currentNode.getLeftChild());
                return true;
            }
        }
        else if(currentNode.getLeftChild() == null) {
            if(root.getData() == currentNode.getData()){
                setRoot(currentNode.getRightChild());
                return true;
            }
            else if(currentNode.getData() < parent.getData()){
                parent.setLeftChild(currentNode.getRightChild());
                return true;
            }
            else{
                parent.setRightChild(currentNode.getRightChild());
                return true;
            }
        }
        else {
            Node leastNode = findLeastNode(currentNode.getRightChild());
            int temp = leastNode.getData();
            delete(temp, root);
            currentNode.setData(temp);
            return true;
        }
    }
    private Node findLeastNode(Node currentNode) {
        Node temp = currentNode;
        while (temp.getLeftChild() != null) {
            temp = temp.getLeftChild();
        }
        return temp;
    }
    public boolean add(int value) {
        if (isEmpty()) {
            root = new Node(value);
            return true;
        }
        Node currentNode = root;
        while (currentNode != null) {
            Node leftChild = currentNode.getLeftChild();
            Node rightChild = currentNode.getRightChild();
            if (currentNode.getData() > value) {
                if (leftChild == null) {
                    leftChild = new Node(value);
                    currentNode.setLeftChild(leftChild);
                    return true;
                }
                currentNode = leftChild;
            } else {
                if (rightChild == null) {
                    rightChild = new Node(value);
                    currentNode.setRightChild(rightChild);
                    return true;
                }
                currentNode = rightChild;
            } 
        } 
        return false;
    }
    public boolean isEmpty() {
        return root == null; 
    }
    public void printTree(Node current) {
        if (current == null) return;
        System.out.print(current.getData() + ",");
        printTree(current.getLeftChild());
        printTree(current.getRightChild());
    }
}

:::