A binary search tree (BST) stores ordered keys so that, for each node, keys in the left subtree compare smaller and keys in the right subtree compare larger according to the chosen ordering.

Searching

At each node, comparing the target key with the current key determines which subtree can still contain the target.

If the tree height is $h$, search takes

$$O(h)$$

comparisons.

Shape determines performance

A well-shaped binary search tree can have height proportional to $\log n$. But inserting already ordered keys into an ordinary BST can produce a chain of height $n$, reducing search to linear time.

Balanced trees

Balanced search trees maintain structural constraints during insertion and deletion so that height stays logarithmic.

Different families—such as AVL and red-black trees—use different balance rules, but share the goal of preventing the search structure from degenerating into a long chain.

Ordered operations

Unlike a hash table, a search tree preserves key order. It can therefore support range queries, predecessor/successor lookup and ordered traversal naturally.