Search:

I spotted your problem. You see, by doing "leafPtr = leaf;" you're not actually changing anything in the binary tree, because you only alter the LOCAL pointer.

Have you overloaded correctly the > and < operators?