# Free a binary tree without using recursion or allocating memory

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;
}
}

• This looks mostly C-ish. Using unique_ptr and the like would be more idiomatic and exception safe, but as you are in a kernel environment, exceptions are not allowed and your recursion requirement rules out the use of unique_ptr. (Then again I am wondering why you are programming C++ in the (supposedly Linux-)kernel) Apr 9, 2014 at 17:58
• @Nobody: You missed the point. using unique_ptr would break the whole concept of not using recursion. Who said Linux and this kernal supports exceptions. Apr 9, 2014 at 17:59
• That is just what I said :) I just wanted to point out that without these restrictions that would be the path to follow. Hence, I made it only a comment and not an answer. Apr 9, 2014 at 18:02
• I can't understand what the question is. Can you make it explicit?
– Juho
Apr 10, 2014 at 13:00
• I like it as it is. And it's already O(n), so you can't get better than that for this. Quick note though, this doesn't compile on Visual Studio 2012, but I doubt that portability is all that important to you. Apr 10, 2014 at 14:59

# 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.

• Comment is correct. The call to findBottomLeft() is not going to de-refernece a NULL if t->right is NULL. Apr 10, 2014 at 19:54
• inlining is a job for the compiler. As a human my job is to write easy to read code. Apr 10, 2014 at 19:54
• The test bl != nullptr should be removed from the loop / inner-loop again, and replaced by the test t != nullptr found at the start of the function in the original, for best performance. May 29, 2014 at 16:15
• A nice way to get around the empty for loop is to use continue as the loop body. May 29, 2014 at 17:18
• @RolandIllig: Some coding standards forbid the use of continue, but there's nothing technically wrong with your suggestion in this instance. May 29, 2014 at 17:40

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.

• While this sounds like a good suggestion, I feel like your answer is missing something. May 29, 2014 at 15:41
• This sounds like a good response but I think maybe it is missing a description of what my answer is missing. Or have I missed your point?
– Ant
May 29, 2014 at 16:25
• It is missing a description of what is missing because I just have a general feeling. I would suggest some code, but It could be just noise. I have no clear idea of what you could do, I was just trying to "warn" you. May 29, 2014 at 16:34