How to empty a Binary Serach Tree???

Well Iīve been working with this Binary Search Tree and it is almost completed. Itīs actually only missing a "cleaning" operation. I am trying to implement a member-fuction for cleanup that actually deletes all nodes in the tree for avoiding a serius memory leak. The problem is that I donīt know how to do it.

I have one solution that deletes the root until the tree is empty but this seems quite un-efficient because the tree must be rebuild every time it deletes the root. I was also thinking to implement a recusive deleteAllNodes member-func but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???. Iīm looking for an iterative solution (if there is any) but I havenīt come up with some.