CODEWITHSUNDEEP
ctree
Memory Leak
Memory Leak

Reputation: 13

How to free a tree?

One recursive function to free an entire tree. One parameter that can take in any node from the tree. Each node contains a pointer to parent node and children nodes. No helper functions and no other parameters.

What I have:

void freeTree(Node *node)
{
  int i, j;
  Node *parent = node->parent;
  for (i = j = 0; i < node->nChild; i++) {
    if (node->child[i]) {
      j++;
      freeTree(node->child[i]);
    }
  }
  if (j != 0 && parent != NULL) {
    freeTree(parent);
  } else {
    free(node);
  }
}

*** Error: double free or corruption (fasttop): 0x000000000XXXXXXX ****

Upvotes: 0

Views: 167

Answers (2)

Atlante45
Atlante45

Reputation: 353

Splitting the code in several function will make it easier to read and understand.

Node* findRoot(Node* node) {
    if (node->parent) {
        return findRoot(node->parent);
    }
    return node;
}

void freeNode(Node* node) {
    int i;
    for (i = 0; i < node->nChild; i++) {
        if (node->child[i]) {
            freeTree(node->child[i]);
        }
    }
    free(node);
}

void freeTree(Node* node) {
    freeNode(findRoot(node));
}

Upvotes: 1

Jason Goemaat
Jason Goemaat

Reputation: 29234

If you were working with the root node it would be easy, just call the function recursively for all children then free the node you are on. It's easy enough to find the root, just recursively call the function with the parent if there is one then return. Once you reach a node with no parent, remove the parent link from all children so they are the roots of their own trees, call the function recursively for them, then free the node you are on.

    A
   / \
  B   C
     / \
    D   E

If you call the function with D or E, it will call itself for C and return. If called with B or C it will call itself with A and return. When called for A since there is no parent, it will remove the parent links from B and C, call itself for B and C, free node A and return. Now that B doesn't have a parent, it will free itself. Since C doesn't have a parent anymore it will remove the parent links from D and E then call itself for those, free node C and return.

void freeTree(Node *node)
{
    int i;

    /* find root node */
    if (node->parent) {
        freeTree(node->parent);
        return;
    }

    for (i = 0; i < node->nChild; i++) {
        node->child[i]->parent = NULL; /* no parent so will free it and children */
        freeTree(node->child[i]);
    }
    free(node);
}

Upvotes: 0

Related Questions