Checkpoint: Walk One Path
intermediate35 min readLesson 126 of 204
BST contains and insert — the ordering discipline that separates O(log n) from O(n) without changing the answer.
bst_contains is the exam because the wrong-looking version passes the
eye test: searching both subtrees returns the same answers. It is just
O(n) instead of O(log n) — and on a degenerate tree, indistinguishable
from linear scan.
The discipline being tested:
- compare, then descend into exactly one subtree
!nis the base case that means "absent", not an errorinsertmirrors the same walk and attaches at the null it reaches
This is the exact trade std::map makes for you: the balanced variant
keeps the tree height logarithmic so every lookup pays O(log n), never
O(n). After this module, you know what you are paying for.