How to print all words in a Trie?

Question

I am trying to create a Trie Implementation in C++. I cannot figure out how to print all words stored in the Trie.

This is how I've implemented the TrieNode.

struct TrieNode{
  bool isWord;
  int data; //Number of times Word Occured
  TrieNode *Child[ALPHABET_SIZE]; //defined as 26
};

I know I could store a pointer to the parent node, Depth-First Search for all nodes where isWord==True and recursively print each word from those nodes.

But I'm wondering is there a way to print out each word in the Trie with my implementation of a TrieNode.

Thanks for any help.

Stylograph

What is data ? I understand isWord and the Child array (why not children ?) gives the children... but what does data stand for ? – Lifeguard

Sorry, for clarification. It is to contain the number of times the word occured in a text document. – Stylograph

Answer 1

Here is a reasonably efficient version of Konrad Rudolph, without assuming data is a character. I also removed the O(n^2) total memory allocated in Konrad's version at the cost of using a std::string&. The idea is to pass down the prefix and modify it at each recursion, pushing characters onto the end and poping it afterwards, ends up being slightly more efficient than copying it madly.

void traverse(std::string& prefix, TrieNode const& node) {
  if (node.isWord)
    print(prefix);

  for (char index = 0; index < ALPHABET_SIZE; ++index) {
    char next = 'a'+index;
    TrieNode const* pChild = node.Child[index];
    if (pChild) {
      prefix.push_back(next);
      traverse(prefix, *pChild);
      prefix.pop_back();
    }
  }
}

Germanize

Note: you could be using a std::string& prefix without loss of functionality, and the code for print would be easier. – Lifeguard

Yes, but then I'd have to look up the right syntax to fake pop_back for std::string, and I was in a rush. Apparently it has since been added to C++11 however? Score! – Germanize

Logic was very helpful for me. Thanks – Stylograph

Answer 2

You don’t need your parent node, your code readily accommodates traversal via recursion. Pseudo-code:

void traverse(string prefix, TrieNode const& n) {
    prefix += static_cast<char>(n.data);

    if (n.isWord)
        print(prefix);

    for (auto const next : n.Child)
        if (next)
            traverse(prefix, *next);
}

This is more or less valid C++. Just define print appropriately.

EDIT In response to Yakk’s comment and your clarification, here’s a version which doesn’t assume that data contains the current character (bad slip on my part!):

void traverse(string const& prefix, TrieNode const& n) {
    if (n.isWord)
        print(prefix);

    for (std::size_t i = 0; i < ALPHABET_SIZE; ++i)
        if (n.child[i])
            traverse(prefix + ('a' + i), *n.child[i]);
}

I’ll leave the more efficient implementation to Yakk’s answer.

Agnes

Why do you assume that data would be a character ? – Lifeguard

@MatthieuM. Because OP said that the structure represents a trie. What else should it be? You need to store the character data of a node somewhere. (But yes, data should be of type char, not int.) – Agnes

@KonradRudolph, see my answer -- the index of the child pointer tells you what the next character is, so you have no need to actually store it in the node. – Germanize

Answer 3

void traversePrint(TrieNode* sr,char* out,int index)
{
    if(sr!=NULL)
    {
        for(int i=0;i<SIZE;i++)
        {
            if(sr->child[i]!=NULL)
            {
                out[index] = 'a'+i;
                traversePrint(sr->child[i],out,index+1);
            }
        }
        if(sr->isEnd)
        {
            out[index]='\0';
            cout << out << endl;
        }
    }
}

// Calling

char out[MAX_WORD_SIZE];
traversePrint(root,out,0);

Isooctane

Answer 4

I dont think isword is needed here. The existence of the pointer to children will be enough to traverse the trie for available words in the trie. to find a word, start from the root and look for the current character within the word during any recursive step.

struct trie {
  trie *children[ALPHABET_SIZE];
};


void traversal(trie *&t, string &str) {
    bool is_seen = false;
    for(int i = 0; i < ALPHABET_SIZE; i++) {
        if(t->children[i]) {
            if(!is_seen) {
               is_seen = true;
            }
            str.push_back(t[i]);
            traversal(t->children[i], str);
            str.pop_back();
        }
    }
    if(!is_seen) {
        cout << str << "\n";
    }

}

Deerskin

Not every node is a word. You have to mark it or use a word_string object to store the word; empty word stands for not having that word in the dictionary. – Karlise