Binary search tree

A node stores a key, associated content, and links to two subtrees. Every key in the left subtree is smaller and every key in the right subtree larger. The invariant covers whole subtrees, not merely the two immediate children.

Search compares a query with the root key, descending left or right as appropriate. Equality finds the item; reaching a null link establishes absence. The same comparisons locate the position where a new key can be inserted.

References: [1]

Inorder traversal visits the left subtree, then the node, then the right subtree. The ordering invariant makes this enumerate keys in increasing order without separately sorting the output.

To delete a node with two children, one method replaces it with its successor, the smallest key in its right subtree, and removes that successor from its former position. Reconnecting both subtrees must preserve the same invariant rather than discarding one branch.

References: [1]

Search can follow a root-to-leaf path, so its cost depends on height. Inserting already ordered keys into an unbalanced implementation can produce a nearly single chain, requiring almost all nodes in a worst-case search.

Favorable average results under random insertion do not guarantee logarithmic work for arbitrary input. Balanced search trees add rules to control height. Having at most two children and having logarithmic height are distinct properties.

References: [1]