Binary Search Tree

A sorted array supports binary search well, but inserting or deleting values in the middle is costly because many elements move. A hash table gives fast lookup on average, but it does not preserve sorted order, which makes range queries and ordered traversal awkward. A BST exists to maintain dynamically changing data together with ordering.

Compilers, symbol tables, memory managers, and early indexing systems needed more than raw lookup speed. They needed insertion, deletion, predecessor and successor queries, and sorted traversal over data that kept changing. Search trees emerged under that pressure, and the BST became the foundational form that later balanced variants built on top of.

Search starts at the root and compares the target key with the current node. If the key is smaller, traversal moves left. If larger, it moves right. Insertion follows the same comparison path until it reaches an empty child position and attaches a new node there. Because the ordering invariant is preserved recursively, an in-order traversal returns the keys in sorted order. If the tree becomes badly skewed, however, the structure collapses toward a linear chain and performance degrades with it.

A BST and a heap are both trees, but they keep different kinds of order. A BST preserves enough global order to support range queries and sorted iteration. A heap preserves only local priority between parent and child so that the top-priority element stays at the root. BSTs also differ from hash tables by preserving order directly instead of optimizing only average key lookup.

BSTs are useful for ordered sets and maps, predecessor or successor lookups, floor and ceiling queries, and range-oriented logic where order itself is part of the problem. Practical systems often use balanced BST variants rather than plain BSTs because skew destroys the expected logarithmic behavior. Even so, the plain BST remains the clearest model for understanding why those balancing strategies matter.