binary search tree
A binary search tree is a binary tree with one extra promise that makes it searchable: for every node, all keys in its left subtree are smaller than the node's key, and all keys in its right subtree are larger. This ordering invariant holds at every node, all the way down. It is the tree-shaped cousin of a sorted array.
That single rule lets you find a key the same way you would play a higher-or-lower guessing game. Start at the root; if your target is smaller, go left, if larger, go right, and stop when you match or run off the bottom. Each step throws away one whole subtree, so when the tree is balanced you halve the candidates every time and a search, insertion, or deletion costs O(log n). Walking the tree in 'left, self, right' order even reads the keys back out in sorted order for free.
The catch is that the speed depends entirely on the tree staying bushy. If you insert already-sorted data into a plain BST, each new key is larger than the last and the tree grows into a single long branch — a degenerate tree — and search collapses back to O(n), no better than scanning a list. This fragility is exactly why balanced search trees were invented: they do extra work on insert to keep the height near log n no matter what order the data arrives in.
Node* find(Node* root, int key) {
while (root != nullptr) {
if (key == root->value) return root;
root = (key < root->value) ? root->left
: root->right;
}
return nullptr; // not found
}Iterative BST search — O(log n) when the tree is balanced.
A balanced BST gives O(log n) search; a degenerate (vine-like) BST drops to O(n) — the invariant guarantees order, not shape.