Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The simplest way to insert an item into a binary search tree is to pretend that the item is already in the tree and then follow the path taken by the Find routine to determine where the item would be. Assuming that the item is not already in the tree, the search will be unsuccessful and will terminate an an external, empty node. That is precisely where the item to be inserted is placed!
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.