Free a Binary Tree

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

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.