Binary Search Tree (BST)

A Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• The left and right subtree each must also be a binary search tree.

This property guarantees that an Inorder Traversal of a BST will always retrieve the elements in sorted order.

Visual Representation

Notice how all values on the right of 8 are >, and on the left are <.

Operations Time Complexity

Operation	Average Case	Worst Case (Degenerated Tree)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Java Implementation

public class BinarySearchTree {
    class Node {
        int key;
        Node left, right;
        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    Node root;

    // Insertion
    public void insert(int key) {
        root = insertRec(root, key);
    }

    private Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key)
            root.left = insertRec(root.left, key);
        else if (key > root.key)
            root.right = insertRec(root.right, key);
        return root;
    }

    // Search
    public boolean search(Node root, int key) {
        if (root == null) 
            return false;
        if (root.key == key) 
            return true;
        if (root.key > key) 
            return search(root.left, key);
            
        return search(root.right, key);
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);

        System.out.println("Search 40: " + bst.search(bst.root, 40)); // true
        System.out.println("Search 90: " + bst.search(bst.root, 90)); // false
    }
}