Binary Search Trees

left < node < right: O(log n) search, sorted inorder.

The idea

A binary search tree stores a set of keys so that we can find any one of them quickly. It is a binary tree — each node holds one key and has at most two children, a left and a right — subject to an ordering invariant: at every node, every key in the left subtree is smaller than the node's key, and every key in the right subtree is larger.

Algorithm.

BST search. The input is a binary search tree and a target key $k$; the output is the node holding $k$, or the report that $k$ is absent. 1. Set the current node to the root. Invariant: if $k$ is anywhere in the tree, it is in the subtree under the current node. 2. If there is no current node — the child the search just called for is missing — stop and report that $k$ is absent. 3. Compare $k$ with the current node's key: — if they are equal, stop and return the current node; — if $k$ is smaller, set the current node to the left child, since the ordering invariant places $k$, if present, in the left subtree; — if $k$ is larger, set the current node to the right child, for the same reason on the other side. 4. Go back to step 2.

Each comparison rules out one whole subtree without examining it, so the search traces a single path from the root downward. It therefore costs one comparison per level, so its cost is the height of the tree. A tree with all levels full has height about $\log_{2} n$ on $n$ keys; a tree that has degenerated into a chain has height $n$, and searching it is no faster than scanning a list.

Ways to work on it

• Walkthrough. The BST invariant and searching in O(height).
• Practice. Decide a search direction at a node.
• Hardest. Cost of an unsuccessful search; the sorted-inorder invariant.

Not sure where to start? Take the ten-question placement test.