Free a binary tree without using recursion or allocating memory

Question

As the title says, the objective is to free a binary tree without using the stack or allocating memory.
This was required for a kernel module where resources were limited.

Result has a complexity of \$ O \left( n \right) \$.

template<typename T>
struct Node
{
    T     data;
    Node* left;
    Node* right;
};

// Utility function to find the bottom left
// Of the tree (because that has a NULL left
// pointer that we can use to store information.
Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

void freeTree(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.    
    Node* bottomLeft    = findBottomLeft(t);


    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        delete old;
    }
}

Answer 1

function missing templates

I'm sure you're aware, but the functions need the same templating as the Node such that void freeTree(Node* t) becomes:

template<typename T>
void freeTree(Node<T>* t)

slight reduction in memory use

You could slightly reduce the stack used by essentially inlining the function call to findBottomLeft. The rewritten function now looks like this:

template<typename T>
void freeTree(Node<T>* t)
{
    // bl points at the bottom left node.
    // Any right nodes from t are added to the bottom left as we go down.
    // This progressively flattens the tree into a list as we go.    
    Node<T> *bl;
    for(bl=t ; bl != nullptr && bl->left != nullptr; bl=bl->left);

    while(t != nullptr)
    {
        // body of for loop deliberately empty
        for (bl->left = t->right; bl != nullptr && bl->left != nullptr; bl=bl->left);
        Node<T>*   old = t;
        // Now just free the curent node
        t = t->left;
        delete old;
    }
}

Note that I'm using nullptr rather than NULL here which is a C++11 feature. If you're not using a C++11 compliant compiler, you can simply use NULL for each of those instances.

Also, I've eliminated the early return in the case that t was equal to NULL in the original because this case is handled correctly by the for loop and while loop.

It's also important to realize that the body of the for loop is deliberately empty. Some people dislike having a for loop with just a semicolon at the end, but I think it's not a problem if there is a comment pointing it out.

Answer 2

If I understand your question correctly, you could build your tree using std::map, std::set or Boost graph library. They have allocators which you could use to allocate from a single pre-allocated block of memory. Your non-recursive free then becomes simply freeing the pre-allocated block. I'm not saying this is a simple approach nor the best for general work but maybe it meets your requirements.