Another algorithm for non-recursively deleting the nodes of a binary tree comes from boost. Reading library code is a bit cumbersome because library code tries to be generic, but if you unwind the traits classes, you get this:

void DeleteTree(Node* node)
{
    while (node) {
        Node* next = node->left;
        if (next) {
            node->left = next->right;
            next->right = node;
        } else {
            next = node->right;
            delete node;
        }
        node = next;
    }
}

If the root node has no left child, then delete it and continue with the right subtree as the new root.

Otherwise, the root node has a left child, so rotate the tree to make that left child the new root.

The order of element destruction produced by this algorithm is inorder. It took a little thinking, before I figured out how to show that the running time is linear in the number of nodes.

If you consider the nodes that are not on the long right chain (the nodes you fail to visit when you start at the root and follow only right links), every rotation decreases the number of those nodes by one. Therefore, you can have at most n rotations before you’ve rotated everything onto the long right chain.¹ (It also means that you can predict the number of rotations by inspection: Count the number of nodes on the long right chain and subtract it from the total number of nodes.)

The other step is the deletion step, and clearly that happens exactly n times.

This algorithm is fairly simple once you figure it out, which makes it easier to implement correctly the first time. It does write two pointers per iteration, so it will fill up the write cache faster than the algorithms that write only one pointer per iteration. (Also, not every iteration leads to a node deletion.) Since the tree keeps rotating in one direction, the written pointers are not revisited until all of the nodes to the left of them have been cleaned up. Conversely, as small subtrees are gobbled up, you get good locality of reference because the same cluster of pointers gets used repeatedly.

¹ Of course, if you know ahead of time that your tree is biased to the left, you can choose the mirror image algorithm so that you have fewer nodes requiring rotation.