How to write destructor for Trie tree

Question

I've been working on an assignment which has us use a trie tree to add words from a dictionary into the tree and then search through it. The part I'm stuck on is the class destructor. This is the first time I've had to deal with a destructor/memory management and what I have below is my best guess after searching through the resources I have at the moment.

Am I on the right track? Each node has 27 children (the alphabet and a delimiter), so I'm hoping it deletes them all from the leaves to the root.

class Trie
{
private:
    TrieNode *_root = nullptr;
    TrieNode *_current = nullptr;
    TrieNode *_child = nullptr;

    string current_word;
    bool setRoot = false;

protected:

public:
    Trie()
    {
        _root = new TrieNode{};
    }

    virtual ~Trie()
    {
        //TODO: clean up memory
        DestroyRecursive(_root);
    }

    void Trie::DestroyRecursive(TrieNode* node)
    {
        if (node != nullptr)
        {
            for (TrieNode* child : node->getChildren())
            {
                delete(child);
            }
        }
    }

How can I check if a destructor is working properly? I'm using Visual Studio.

Answer 1

Your DestroyRecursive is not actually recursive

You need to call delete on the leaf nodes and recurse on nodes with children.

void Trie::DestroyRecursive(TrieNode* node)
{
    if (node != nullptr)
    {
        if (node->getChildren().size() == 0)
        {
            // delete the leaf node
            delete(node);
            return;
        }

        for (TrieNode* child : node->getChildren())
        {
            DestroyRecursive(child);
        }
    }
}

This may go wrong depending on what dependencies on the structure of your TrieNode. For eg does it have a non-trivial destructor?

A lot of this could be avoided by replacing the raw pointer to std::shared_ptr

std::shared_ptr<TrieNode> _root = nullptr;
vector<shared_ptr<TrieNode>> _child = nullptr;

Trie()
{
    _root = std::make_shared<TrieNode>();
}

Then for most cases you wont need a destructor. std::vector and shared_ptr will take care of calling delete on the appropriate memory when going out of scope. Be careful that there is no cyclic dependency in ownership. If you add a parent pointer in future, it has to be either a raw pointer or a std::weak_ptr

How can I check if a destructor is working properly? I'm using Visual Studio.

You can put a breakpoint to check if the code is getting hit.