CODEWITHSUNDEEP
c++data-structurestrie
Anthony Rossello
Anthony Rossello

Reputation: 219

Print out all words in a Trie implemented with a map

I have a TrieNode class defined as follows:

class TrieNode {
public:
    map<char, TrieNode*> children;
    bool isLeaf = false; // if node represents end of word
    int wordCount = 0; // How many times the word appears
    TrieNode();
};

I'm trying to print out all of the words in the trie (preferably in alphabetical order, although I'd settle for anything at this point). I've been trying to implement a recursive solution, but I haven't been able to make a decent start.

EDIT: I should mention that all the other questions I've looked at for how to print all words in a trie store children as an array, rather than a map.

Upvotes: 1

Views: 439

Answers (2)

Christopher Oicles
Christopher Oicles

Reputation: 3107

Here's a depth-first recursive traversal. It would be best not to use raw pointers, but I did it here because you asked and I like you. I did not delete the child nodes allocated by AddTrie, because I just wanted to demonstrate the traversal, rather than write an entire implementation. So, you need to add code to delete these if you use this.

#include <iostream>
#include <map>
#include <string>

class TrieNode {
public:
    std::map<char, TrieNode*> children;
    bool isLeaf = false; // if node represents end of word
    int wordCount = 0; // How many times the word appears
    TrieNode() {}
};

void AddTrie(TrieNode& trie, const char* word) {
    auto c = *(word++);
    auto next = trie.children[c];
    if(!next) { trie.children[c] = next = new TrieNode; }
    if(*word) { AddTrie(*next, word); }
    else      { next->isLeaf = true; }
}

void DumpTrie(const TrieNode& trie, std::string word={}) {
    for(const auto& child : trie.children) {
        const auto next_word = word + child.first;
        if(child.second->isLeaf) { std::cout << next_word << '\n'; }
        DumpTrie(*child.second, next_word);
}   }

int main() {
    TrieNode trie;
    AddTrie(trie, "goodbye");
    AddTrie(trie, "hello");
    AddTrie(trie, "good");
    AddTrie(trie, "goodyear");
    DumpTrie(trie);
}

Output

good
goodbye
goodyear
hello

Upvotes: 1

AdaShoelace
AdaShoelace

Reputation: 342

I assume you want to waste less memory than a 26 slot array in each node by using a map instead? But seeing how maps initial construction cost is pretty high you might want to use a mutual map for all nodes instead of storing one in each node.

Upvotes: 0

Related Questions