Freeing a binary tree data structure in C

Question

I have this function that I hope to be a good alternative to the recursive (thus performance expensive) approach.

#define _free_all(node, yes_no) \
    do { \
        Tree *__i;
        for (__i = node; __i; __i = __i->yes_no); \
        free(; node != __i; __i = __i->parent) { \
            free(__i->value); \
            free(__i); \
        } \
    } while (0)

void Tree_destroy(tree)
    Tree *tree;
{ /* Destroys a Tree object - Non Recursive */
    if (!tree)
        return;
    _free_all(tree, yes);
    _free_all(tree, no);

    if (tree->parent) {
        if (tree->parent->no == info)
            tree->parent->no = NULL;
        else
            tree->parent->yes = NULL;
    }
    free(tree);
}

The two children of each parent are no and yes.

Are there any issues with this approach ?

Answer 1

1. Bug

JS1 is quite correct to point out that this does not work: it never visits or frees tree->yes->no (among other nodes).

2. Correct algorithm

Consider a finite state machine with three states:

1. If tree has a left child, set tree to its left child and go to state 1. Otherwise, go to state 2.

2. If tree has a right child, set tree to its right child and go to state 1. Otherwise, go to state 3.

3. (In this state tree has no children.) Destroy tree. If tree had no parent, stop. Otherwise, delete whichever of parent's children is equal to tree, set tree to parent and go to state 1.

This state machine walks the tree in post-order, destroying each node after destroying all of its descendant nodes. Here's one way of translating this into C:

void TreeDestroy(Tree *tree)
{
    for (;;) {
        if (tree->left) {
            tree = tree->left;
        } else if (tree->right) {
            tree = tree->right;
        } else {
            Tree *parent = tree->parent;
            free(tree->value);
            free(tree);
            if (!parent)
                break;
            else if (parent->left == tree)
                parent->left = NULL;
            else if (!parent->left && parent->right == tree)
                parent->right = NULL;
            else
                assert(0); /* can't happen if tree is well-formed */
            tree = parent;
        }
    }
}

(I've used "left" and "right" here because these are the more usual names for the two children of a node in a binary tree.)

3. What if there are no parent pointers?

To iteratively destroy a binary tree with no parent pointers, start with the rotate right operation:

void TreeRotateRight(Tree **tree)
{
    Tree *left = (*tree)->left;
    (*tree)->left = left->right;
    left->right = *tree;
    *tree = left;
}

By repeatedly applying the rotate right operation, you can turn a tree into a vine. (A vine is a degenerate tree in which nodes only have right children.)

void TreeToVine(Tree **tree)
{
    while (*tree) {
        while ((*tree)->left)
            TreeRotateRight(tree);
        tree = &((*tree)->right);
    }
}

And then a vine is easy to destroy iteratively:

void TreeDestroy(Tree *tree)
{
    TreeToVine(&tree);
    while (tree) {
        assert(!tree->left);
        Tree *right = tree->right;
        free(tree->value);
        free(tree);
        tree = right;
    }
}