Free a binary tree without recursion

Question

refering to the question Deallocating binary-tree structure in C

struct Node{
    Node *parent;
    Node *next;
    Node *child;
}

I tried to free a binary tree. The problem I have is the allocated objects are 5520 and the number of calls to the free functions is 2747. I don't know why, it should really free and iterate all over the nodes in the tree, here is the code that I use

int number_of_iterations =0;
int number_of_deletions =0;
    void removetree(Node *node)
    {
        number_of_iterations++;
        while(node != NULL)
        {
            Node *temp = node;

            if(node->child != NULL)
            {
                node = node->child;
                temp->child = node->next;
                node->next = temp;
            }
            else
            {
                node = node->next;
                remove(temp);
                number_of_deletions++ 
            }
        }
    }

Number of iteration is 5440 and the number of deletions is 2747.

New Fixed code: is that code correct ?

 const Node *next(const Node *node)
    {
        if (node == NULL) return NULL;
        if (node->child) return node->child;

        while (node && node->next == NULL) {
            node = node->parent;
        }

        if (node) return node->next;
        return NULL;
    }

 for ( p= ctx->obj_root; p; p = next(p)) {
      free(p);
     }

Answer 1

If your nodes do indeed contain valid parent pointers, then the whole thing can be done in a much more compact and readable fashion

void removetree(Node *node)
{
  while (node != NULL)
  {
    Node *next = node->child;

    /* If child subtree exists, we have to delete that child subtree 
       first. Once the child subtree is gone, we'll be able to delete 
       this node. At this moment, if child subtree exists, don't delete
       anything yet - just descend into the child subtree */

    node->child = NULL;
    /* Setting child pointer to null at this early stage ensures that 
       when we emerge from child subtree back to this node again, we will 
       be aware of the fact that child subtree is gone */

    if (next == NULL)
    { /* Child subtree does not exist - delete the current node, 
         and proceed to sibling node. If no sibling, the current 
         subtree is fully deleted - ascend to parent */
      next = node->next != NULL ? node->next : node->parent;
      remove(node); // or `free(node)`
    }

    node = next;
  }
}

Answer 2

This is a binary tree! It's confusing people because of the names you have chosen, next is common in a linked list but the types are what matters and you have one node referencing exactly two identical nodes types and that's all that matters.

Taken from here: https://codegolf.stackexchange.com/a/489/15982 which you linked to. And I renamed left to child and right to next :)

void removetree(Node *root) {
    struct Node * node = root;
    struct Node * up = NULL;

    while (node != NULL) {
        if (node->child != NULL) {
            struct Node * child = node->child;
            node->child = up;
            up = node;
            node = child;
        } else if (node->next != NULL) {
            struct Node * next = node->next;
            node->child = up;
            node->next = NULL;
            up = node;
            node = next;
        } else {
            if (up == NULL) {
                free(node);
                node = NULL;
            }
            while (up != NULL) {
                free(node);
                if (up->next != NULL) {
                    node = up->next;
                    up->next = NULL;
                    break;
                } else {
                    node = up;
                    up = up->child;
                }
            }
        }
    }
}