I don't understand how a trie works. Please help

Question

I am on pset5 and have completed the check and load functions. However, with the unload function I am having trouble understanding how to visualize it. As suggested in the walkthrough, I tried to implement the recursion method but I do not understand how that can work. So, we are on the root node with 27 elements in the children array. We point at one of the elements and check if they are NULL. If not, then we apply recursion. What I do not understand is how do we reach the children array of the first children element of the root node with recursion? When we apply recursion, to me, it seems that we keep checking if the same element of the root node is NULL or not but how does that help since we need to reach inside the children element of all the subsequent nodes and free them?

This is my code for the unload function. However, I keep running into an error with valgrind. It says that I have accessed 8 bytes of memory that is not mine.

void delete_node (node *trie)
{
  for (int i = 0; i < 27; i++)
  {
    if (trie -> children[i] != NULL)
    {
        delete_node(trie -> children[i]);
    }
  free(trie);
  }
}

bool unload(void)
{
  node * trav = root;
  delete_node(trav);
  return true;
}

Brief explanation of my code the way I get it. Please correct me if there is something wrong with it - Create a function to free nodes and run it through all the children of the node. If the children is not NULL, call it recursively till you reach a children element that is NULL. Then free it. (If not NULL, keep calling recursively, else if NULL, then free it). Call the function in unload and, using traversal pointer, free all the nodes and return true.

Answer 1

You've essentially explained it, but let's try again. Let's assume the recursive function is named unld(). It starts at the root node. When the first non-null child is found, unld(child-1) is called. This saves the current state of all the vars and memory for the original execution of unld(root) and opens a new copy of unld with all new vars. It will then look for the first child of child-1. If there is a child, i.e., a grandchild of root, then it will step down into that level, and will keep going until it gets to the bottom. When the recursion gets to the bottom, where there are no more descendants, (and assuming it is correctly written), then unld(last-descendant) will free last-descendant.

At this point, the recursion will return, or move back up one level. At this level, unld will move to the next child at this level. If it's not null, it will call unld for the non-null child and again cycle down to the bottom. If null, it will keep moving through the children at that level until all have been cleared. Once all the children are cleared, it will then return up one level and continue the process. This goes on until the process returns to the root node. Having cleared all the branches out, it will then free node and the process ends.

A good visual is this. Draw the tree out on paper. Now, place your pencil on the paper to the left of the root node. Next, without lifting the pencil, draw a single, continuous line along the tree. Stay as close to the tree as possible, moving down the left side, then up in between nodes and down again between leaves and branches. By doing this, the line will pass every node.

As the pencil line passes each node while moving UP, that node would be deleted by the program. This demonstrates the progression of the recursion.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)