0

I haven't written any code yet, although I've written pseudocode for this problem, and I keep coming back to the issue of base case. I built a trie and now want to recursively unload it. I think I've got a handle on the recursive statements but my stumbling block is initializing "current" or "index" without starting all over again each time I recursively call my function. I've avoided looking at other answers to this, because I want to try and work it out, but if anyone can ask question that will help me think about this properly, that would be a big help.

  • Suggest that you ask on one of the more interactive forums, like CS50 Slack. – Cliff B Jun 30 '17 at 21:50
0

It may help to visualize the trie in your head (or on paper) to think about how you want to go about deleting each node. I think Doug Loyd explains it pretty well in his trie short where he describes the trie as a sort of upside down tree where the root node is at the top which then branches out through its children to eventually reach the leaves which are the last nodes (with true or false bool in this case).

So you might want to think about the base case as running out of new nodes in each specific branch to delete. For example if you have two words in you trie say "at" and "for", your root node's children would be all NULL except for entry "a" and "f". Therefore a base case could check that any index in a node is NULL because that would either mean no word starts with that letter say "b", or that the word is in fact finished. In the word "at" your recurive function could call itself until it finds that there is no node extending from "t" in which case it will delete nodes all the way up the branch from the leaf up by the nature of how recursion works.

Of course it gets a bit more complicated when there are multiple words that start with the same letters "at" and "arm", but the same principle of recursion checking for NULL as the base case should work the same as the function will travel down the whole "arm" series of letters, delete "m" node, but will then have a choice between going to the "r" or "t" node first, delete that whole branch (and possibly any others down the line), before returning to the node it didn't choose before and continuing the process.

It is your choice how you want to implement this, but I figure it should work any way you decide to choose the next nodes to delete in the trie as long as you are consistent, for example starting at "z" words and always picking last characters in the alphabet first or vice versa.

And as for indices, you could just start from the left most or the rightmost side of your trie (assuming you implemented in alphabetical order) and decrement or increment as needed to go through all values of the alphabet and the apostrophe. If you already completed the check() and load() functions then you have an idea about how you structured your trie, and can build from there. Hopefully that makes sense without being confusing, and hopefully I am right about how recursion in this case could work, but I may be wrong at a few points since I'm not that experienced with it myself!

Feel free to ask questions in the comments for clarification.

| improve this answer | |
  • I think I want to be able to skip the root part. Because say if I start with current = root in my function in order to begin traversing the nodes, every time I start my function current gets reset back to root which I don't want because I want to step back through my tree and proceed from the directly previous node after I free something. For example: root->child -- not null, root->child->child not null, root->child->child->child is null. so I delete that last child. Then I want to start over only from root->child->child to check the next child in the trie. Not start over with root. – KitSeason Jul 1 '17 at 2:45
  • Yeah you are right, each time you delete a child and free it, you then move on to the next child up the tree, not all the way back to the root. That is why recursion works well on this problem, because deleting the root node happens at the very end as the call to delete the trie's root happens last because it was the first called. Assuming you are using some sort of loop to go through all of the children in each node, your function shouldn't reach the root until it has already checked if each of its children are NULL at which point all of the words in your trie would already be deleted. – dumbitdownjr Jul 1 '17 at 17:59
  • I thought the point of recursion was to recall the function? And if I'm re-initializing current to root each time I recall the function, doesn't that defeat the purpose? Or can the recursion happen within the function without recalling the function? If that's the case, I think I can figure that out. – KitSeason Jul 1 '17 at 18:45
  • You wouldn't want to initialize current to root each time, instead you could call the function passing into it the next child you want to delete (as long as it isn't NULL). As you say the whole point of recursion is to recall the function, but it is dynamic in that you can call it by passing in where you want the function to look next. – dumbitdownjr Jul 1 '17 at 19:25
  • The assignment says we're not to change the function headers. Unload reads "bool unload(void)" A work around would be to create another function that if true makes the unload function true. So basically the unload function's only argument would be the bool from the added function. Otherwise, I'm not sure how to work around it. – KitSeason Jul 1 '17 at 20:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .