Insert into a BST

Smaller values live on the left, bigger on the right, so the new value has exactly one place to go. parent walks down from the root, one comparison per level, until the side it would take is empty.