current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 11 down vote favorite

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;
    }
}
share|improve this question
    
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) –  Nobody Apr 9 at 17:58
1  
@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. –  Loki Astari Apr 9 at 17:59
1  
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. –  Nobody Apr 9 at 18:02
    
I can't understand what the question is. Can you make it explicit? –  mrm Apr 10 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. –  jliv902 Apr 10 at 14:59
add comment

2 Answers

up vote 1 down vote

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.

share|improve this answer
    
While this sounds like a good suggestion, I feel like your answer is missing something. –  Marc-Andre May 29 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 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. –  Marc-Andre May 29 at 16:34
add comment
up vote 5 down vote

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.

share|improve this answer
    
+1 Great catch on the dereferencing NULL. –  jliv902 Apr 10 at 16:03
    
Comment is correct. The call to findBottomLeft() is not going to de-refernece a NULL if t->right is NULL. –  Loki Astari Apr 10 at 19:54
    
inlining is a job for the compiler. As a human my job is to write easy to read code. –  Loki Astari Apr 10 at 19:54
    
@LokiAstari: you're right that my comment about dereferencing NULL is incorrect. I'll delete it from my answer. Your second point also has merit. It depends on both your compiler and the resources available to the code at runtime. If they're very tight, one might even use assembly language. –  Edward Apr 10 at 20:10
    
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. –  Deduplicator May 29 at 16:15
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.