Search code examples
c++data-structuresstltrie

How to traverse a trie to display all the words?


Here's my declaration of a trie in C++ using unordered_map

class trie{
    public:
    unordered_map<char,trie*>m;
    bool isEnd;
};

Here's my insert function(part of another class)

 trie *root=nullptr;
    trie *getNode()
    {
        trie *tmp=new trie();
        tmp->isEnd=false;
        return tmp;
    }
    void insert(string s)
    {
        if(!root)
            root=getNode();
    trie *tmp=root;
    for(int i=0;i<s.length();i++)
    {
        if(tmp->m.find(s[i])==tmp->m.end())
            tmp->m[s[i]]=getNode();
        tmp=tmp->m[s[i]];
    } 
    tmp->isEnd=true;
    }

How to traverse this trie recursively or iteratively to display all the words.


Solution

  • void iterate_(const trie* node, const std::string& prefix) {
      if (node->isEnd) {
        std::cout << prefix << std::endl;
      }
      for (const auto& [c, child] : node->m) {
        iterate_(child, prefix + c);
      }
    }
    
    void iterate() {
      if (root) {
        iterate_(root, "");
      }
    }