14
\$\begingroup\$

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;
    }
}
\$\endgroup\$
6
  • \$\begingroup\$ 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) \$\endgroup\$ Apr 9 '14 at 17:58
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Apr 9 '14 at 17:59
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Apr 9 '14 at 18:02
  • \$\begingroup\$ I can't understand what the question is. Can you make it explicit? \$\endgroup\$
    – Juho
    Apr 10 '14 at 13:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – jliv902
    Apr 10 '14 at 14:59
6
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Comment is correct. The call to findBottomLeft() is not going to de-refernece a NULL if t->right is NULL. \$\endgroup\$ Apr 10 '14 at 19:54
  • \$\begingroup\$ inlining is a job for the compiler. As a human my job is to write easy to read code. \$\endgroup\$ Apr 10 '14 at 19:54
  • \$\begingroup\$ 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. \$\endgroup\$ May 29 '14 at 16:15
  • \$\begingroup\$ A nice way to get around the empty for loop is to use continue as the loop body. \$\endgroup\$ May 29 '14 at 17:18
  • \$\begingroup\$ @RolandIllig: Some coding standards forbid the use of continue, but there's nothing technically wrong with your suggestion in this instance. \$\endgroup\$
    – Edward
    May 29 '14 at 17:40
2
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ While this sounds like a good suggestion, I feel like your answer is missing something. \$\endgroup\$
    – Marc-Andre
    May 29 '14 at 15:41
  • \$\begingroup\$ 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? \$\endgroup\$
    – Ant
    May 29 '14 at 16:25
  • \$\begingroup\$ 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. \$\endgroup\$
    – Marc-Andre
    May 29 '14 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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