Binary Search Tree

How it works

A BST keeps elements ordered: every left descendant is smaller, every right descendant larger. That invariant turns search, insert, and delete into a single root-to-leaf walk — O(log n) when balanced, but O(n) if it degenerates into a line.

Mental models

• At each node you discard half the tree — that's the log n.
• In-order traversal (left, node, right) prints values sorted.
• Self-balancing variants (AVL, Red-Black) guarantee log n height.

Common pitfalls

• Inserting sorted data builds a linked list — O(n) operations.