A tree that keeps things in order

A hash table finds a key instantly and has no order at all. A sorted array has order and costs O(n) to insert into. A binary search tree is the attempt to have both.

The rule

One rule, applied at every node:

everything in the left subtree is smaller, everything in the right subtree is larger

              50
           /      \
        30          70
       /  \        /  \
     20    40    60    80

Searching for 40: start at 50, smaller so go left; at 30, larger so go right; found. Three comparisons instead of seven, because each step discarded half of what was left.

def search(node, target):
    if node is None or node.value == target:
        return node
    if target < node.value:
        return search(node.left, target)
    return search(node.right, target)

What it buys

That last row is the reason to choose a BST over a hash table. Walking it inorder produces every key in sorted order, and answering "give me everything between 20 and 40" is a single traversal. A hash table cannot do either without sorting everything first.

The catch, and it is a real one

Insert 10, 20, 30, 40, 50 in that order into an empty BST. Every value is larger than the last, so every node goes right, and the result is a linked list with extra pointers. Search is now O(n).

This is not a rare case. Data arriving in sorted order is extremely common, which means the naive BST fails precisely when the input is tidy.

Self balancing

Real implementations rebalance as they go. An AVL tree keeps the two subtree heights within one of each other. A red black tree uses a colour rule that is looser and so rebalances less often, which is why it is what most standard libraries actually use: C++ std::map, Java TreeMap.

You are rarely asked to implement one. You are frequently asked why a plain BST is not good enough, and the answer is the sorted input above.