>>I have one solution that deletes the root until the tree is empty

Eew, yucky! Why not just use an in-order traversal and instead of doing something fun with the node, delete it. :-)

Code:

void destroy(tree *t)
{
if (t == 0)
{
return;
}
destroy(t->left);
destroy(t->right);
delete t;
}

>>but isnīt this also quite un-efficient if the tree contains MANY nodes (invokes many functions)???.

Not enough to worry about unless you've fallen into the worst case of ordered insertion where the tree depth is equal to the number of nodes. If this is even close to possible you need to use a balanced insertion algorithm to begin with. Otherwise, a recursive routine only has a depth equal to the height of the tree. Even for **HUGE** trees this won't be noticeable.