What are the main characteristics that distinguish a binary search tree?

A Binary Search Tree (BST) has the following main characteristics:

• Each node contains a key (value).
• For any node, all keys in the left subtree are less than the key of that node.
• All keys in the right subtree are greater than the key of that node.
• The left and right subtrees are also binary search trees.

This allows efficient search, insertion, and deletion operations with an average complexity of O(log n), if the tree is balanced.

Example of inserting into a BST in Java:

class Node {
    int key;
    Node left, right;

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

class BST {
    Node root;

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

    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;
    }
}