TREE-INSERT with a trailing pointer (CLRS, iterative)

Answer

TREE-INSERT(T, z): y = NIL x = T.root while x != NIL: y = x if z.key < x.key: x = x.left else: x = x.right z.p = y if y == NIL: T.root = z elif z.key < y.key: y.left = z else: y.right = z

y trails one step behind x; when x falls off the tree, y is exactly the parent to attach z under as a leaf. O(h) — the cost of one root-to-leaf descent.