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:
If tree has a left child, set tree to its left child and go to state 1. Otherwise, go to state 2.
If tree has a right child, set tree to its right child and go to state 1. Otherwise, go to state 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;
}
}
Info
andTree
defined? \$\endgroup\$ – Olaf Dietsche Nov 14 '14 at 22:45_
and__
are reserved and best if avoided. \$\endgroup\$ – glampert Nov 15 '14 at 1:30free_all
macro either frees only left nodes or only right nodes, which means that any node in your tree that isn't on the left edge or right edge won't be freed. \$\endgroup\$ – JS1 Nov 15 '14 at 10:50