Non-recursively deleting a binary tree in constant space: Traversal with parent pointers

As a challenge, a colleague of mine told me to find a non-recursive constant-space algorithm for deleting a binary tree.¹

After a moment’s thought, I was able to come up with an algorithm. It is often the case that solving a problem is easier once you are told that a solution exists.

When I asked the Internet for a non-recursive constant-space algorithm, it seems that everybody uses an algorithm different from the one I found, so let’s look at that one first.

The idea behind that algorithm is to start with the algorithm for iteratively traversing a binary tree in which each node also remembers its parent. The linked article does an inorder walk, so we’ll adapt the N-ary postorder walk.

struct Node
{
    Node* left;
    Node* right;
    Node* parent;
    Data d;
};

void DeleteTree(Node* node)
{
    while (node) {
        // Go left as far as you can.
        while (node->left) {
            node = node->left;
        }

        // If you can't go left, try going right one step,
        // and then continue the leftward descent.
        if (node->right) {
            node = node->right;
            continue;
        }

        // At the bottom. Delete the node and head back up.
        while (node) {
            auto parent = node->parent;
            delete node;
            if (!parent) {
                return; // all done
            }
            // If we came from the left child,
            // then go to the right child if there is one.
            if (node == parent->left && parent->right) {
                node = parent->right;
                break;
            } else {
                // No more children, so keep walking up.
                node = parent;
            }
        }
    }
}

The only tricky part is that our N-ary postorder walk wants a NextSibling, but we don’t have that. We synthesize it by realizing that in a binary tree, each parent has only two children, so if you are a child, you are either the left child (in which case the next sibling is the right child, if you have one) or the right child (in which case there is no next sibling). You can figure out which one you are by seeing if you are your parent’s left child.

Next time, we’ll figure out where to get the parent pointer when we don’t have one.

¹ You might be in need of such an algorithm if your tree can get very deep, so a recursive algorithm would exceed available stack space. The constant space requirement is important because this ensures that you don’t run into a low-memory error when trying to free up memory. C++ destructors are noexcept by default, and even if you mark them as potentially-throwing, throwing an exception from a destructor that is called due to unwinding is considered a fatal error that results in immediate termination of the program. Clean-up functions cannot fail.