13
\$\begingroup\$

So before you read some basic computer science concepts.

  1. A binary tree is a dynamically allocated structure (usually used for ordered storage).
  2. Because of its nature traversal of binary trees is usually recursive;
    This is because linear traversal (via a loop) is not natural when there are two avenues of looping.
    • Recursive: This means a function that calls itself.
  3. In old fashioned languages, memory management requires manual memory management.
    • Manual: Means you have to do it yourself.
  4. When you do manual memory management you need to actual ask the underlying system to free each member of the tree.
    • Free: recover the memory in to the global poos so it can be re-used and you don't run out of memory.
    • Freeing: this is done by calling the function free() and passing it the pointer you want to recover.
    • Pointer: Its like a virtual stick. At the end is memory. When you ask for memory you are given a pointer (virtual stick) that has memory. When you are done you give back the pointer (virtual stick).

The recursive solution:

freeTree(Node* node)
{
    freeTree(node->left);  
    freeTree(node->right);
    free(node);
}

The problem then is that recursion means you are repeatedly calling the same function. This grows the stack. Growing the stack uses more memory. The reason you are freeing the tree is you want memory back using more memory is counterproductive (even if you do get both bits of memory back).

At last the question:

SO the problem centers around converting the recursive version above into a linear solution (so that you don't have to use memory).

Give the node type

typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

Write a function to free a tree of these nodes.

Restrictions:

  • Cannot use recursion (not even indirectly)
  • Cannot allocate any dynamic space for tracking.

  • Note there is an O(n) solution

Winner:

  1. Best Complexity.
  2. Tie Break 1: First Submitted
  3. Tie Break 2: Least amount of characters.
\$\endgroup\$
7
\$\begingroup\$

Seems very close to O(n) to me:

This does a depth-first walk on the tree, and uses the ->left pointer of traversed nodes to keep track of the parent.

struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ +1 Add the tick for the only answer. Its a bit more complex than the solution I present below but very good. \$\endgroup\$ – Martin York Feb 7 '11 at 20:49
4
\$\begingroup\$

C99, 94, O(n)

Edit: everyone seems to refer to struct Node just as Node as if the typedefed it, so I did too.

this is actually my first C golf. lots of segfaults.

anyways, this requires C99 because it uses a declaration inside a for loop's first statement.

void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

not even using #define!

this algorithm works by transforming the tree so that the top node has no left child, and then deleting it and moving on to it's right child.

for example, if we start with the tree

 1
/ \
2 3
 \
 4

the algorithm will mutate the pointers so that the tree will be

2
 \
 1
/ \
4 3

now we can delete the topmost node easily.

\$\endgroup\$
  • \$\begingroup\$ I did not use typedef because mine was in C++ (you forget these small differences between the languages). I have updated the question so it works the same in C and C++. \$\endgroup\$ – Martin York Dec 25 '14 at 18:36
  • \$\begingroup\$ @LokiAstari I don't actually know c++, and I just started learning C recently. But I did know enough to answer this :-) \$\endgroup\$ – proud haskeller Dec 25 '14 at 18:38
  • 1
    \$\begingroup\$ I am going to do a +1 for now. But I still have not worked out how it is working so I will be back after turkey. :-) \$\endgroup\$ – Martin York Dec 25 '14 at 18:40
  • \$\begingroup\$ @LokiAstari it basically uses the fact that C mixes expressions and statements together to do thing using only expressions \$\endgroup\$ – proud haskeller Dec 25 '14 at 18:42
1
\$\begingroup\$

C/C++/Objective-C 126 characters (includes required trailing newline)

#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

Does not run in O(n) time. But the OP does not require it, so here's my O(n2) solution.

Algorithm: Walk down to a leaf from the root. Release it. Repeat until there are no leaves. Release the root.

Ungolfed:

void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}
\$\endgroup\$
  • \$\begingroup\$ Unfortunately that will not work. you don't set the pointer to the leaf to NULL before freeing it. Thus you will endlessly keep freeing the same leaf node and never get to the point where you free the tree. \$\endgroup\$ – Martin York Dec 23 '14 at 19:46
  • \$\begingroup\$ @LokiAstari: Thanks for noticing the bug. It should be fixed now (though I haven't tested the code). \$\endgroup\$ – Thomas Eding Dec 23 '14 at 21:47
1
\$\begingroup\$

c++ 99 O(n)

The thing here loops are great for chaining along a list but not going up and down hierarchies. user300 managed it (I am impressed) but the code is hard to read.

The solution is to convert the tree into a list.
The trick is to do it at the same time your deleting the nodes.

void freeNode(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;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

Golf Version

void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

Golf Expanded

void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}
\$\endgroup\$
0
\$\begingroup\$

C, 150 bytes

f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

Try It On JDoodle

\$\endgroup\$

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.