Recursive Tree Search

Searching in a binary tree: compare the key with the current node and descend left or right. Without the search tree invariant, only complete traversal remains.

Task: count the nodes of a binary tree recursively.

$$x \lt k \Rightarrow \mathrm{left}$$

Where used

BST lookup is the model behind TreeMap and many indexes. The same idea scales to B-trees on disk and to space-partitioning trees (k-d, Quadtrees) in games and GIS.

Depth

A general tree search checks the current node and searches both subtrees if necessary. In a search tree, however, the ordering invariant allows excluding exactly one subtree based on a comparison.

The runtime is proportional to the structure visited. In a well-formed tree, the search path length corresponds to the height; in a one-sided tree, almost every node may need to be checked. Balance is therefore a runtime property of the shape, not of the recursive syntax.

For object keys, the comparison relation must be consistent. A comparison value of zero specifies when the search considers a hit and thus affects the treatment of technically identical keys.

Difficulty levels

1. Distinguish between general and ordered searches.
2. Track a search path based on comparisons.
3. Explain shape-dependent worst-case costs.

Pitfalls

Without a proven ordering invariant, no subtree may be excluded. Incorrect treatment of the comparison sign can also render existing keys invisible.