The same 63 keys, inserted in two orders

The same 63 keys, inserted in two orders

Both trees hold the keys 0 to 62. On the left they arrived in order, and the tree has height 62 — every node has one child, and a lookup costs a linear scan. On the right the same keys arrived shuffled, giving height 10 against an ideal of 5. Both figures are truncated at depth 16 because the left one does not fit. The logarithmic lookup a binary search tree is chosen for is a property of the insertion order, not of the structure.

Drawn at 700 × 400, wide on the page. Everything above is what tree-shape returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

4 essays call tree-shape. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.