DWG. 04 — BINARY SEARCH TREE

Two Trees

The same values, twice. On the left, built by taking the middle value as the root and repeating. On the right, built by inserting the values one at a time in sorted order — which is a linked list wearing a tree costume.

Search both at once and count the comparisons. That gap is the entire reason isBalanced and rebalance exist.

balanced

0comparisons

height 0

ready

degenerate

0comparisons

height 0

A — buildTree(values) middle value as root, recursively

B — insert() in sorted order every value is larger than the last, so every value goes right

structure

Binary search tree

search, balanced

O(log n)

search, degenerate

O(n)

notes

Both trees hold identical values and both obey the search rule. Only the shape differs. Press rebalance to rebuild B from its own in-order traversal.