http://kor.i2p/books/The%20C%20Programming%20Language%20by%20K&R/chapter6.html
If the new record is less than the tree
word, continue searching at the left child, otherwise at the right child. If
there is no child in the required direction, the new word is not in the tree,
and in fact the empty slot is the proper place to add the new word.