calgorithm

Free a binary tree without recursion


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

Solution

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