Free a Binary Tree [closed]

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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(n²) 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);
}

Answer 5

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