May 012017
 

Given a collection of words stored in a Trie data structure, write a function that print all the words stored in it. For example, If the Trie is

Then output should be:

at
ate
bad
bed
beat
beard

Like all Tree algorithm this also uses recursion. There are just few points:

  • Use an array to store the characters of nodes in path (parent node values).
  • If the current node is end-of-word then print the values in path array.
  • else, add the current char to array, and call the function recursively for all child node.

Below is the code for same:

// Helper function to print the word found
void printWord(char* str, int n)
{
    cout<<endl;
    for(int i=0; i<n; i++)
    {
        cout<<str[i]<<" ";
    }
}

// Print all words in Trie
void printAllWords(TrieNode* root, char* wordArray, int pos = 0)
{
   if(root == NULL)
      return;
   
   if(root->isEndOfWord)
   {
      printWord(wordArray, pos);
   }
   for(int i=0; i<NO_OF_ALPHABETS; i++)
   {
      if(root->child[i] != NULL)
      {
         wordArray[pos] = i+'a';
         printAllWords(root->child[i], wordArray, pos+1);
      }
   }
}

Below is the complete running code with

#include <iostream>

using namespace std;

#define NO_OF_ALPHABETS 26
#define MAX_WORD_SIZE 100

// TrieNode structure
struct TrieNode
{
   TrieNode* child[NO_OF_ALPHABETS];
   bool isEndOfWord;
   
   // Default constructor, set all the child nodes to NULL
   TrieNode():isEndOfWord(false){
      for(int i=0; i<NO_OF_ALPHABETS; i++)
         child[i] = NULL;
   }
};

// Insert the word in Trie
void insert(TrieNode* root, char* word)
{
   for(int i=0; word[i] != '\0'; i++)
   {
      if(root->child[word[i]-'a'] == NULL)
      {
         root->child[word[i]-'a'] = new TrieNode;
      }
      root = root->child[word[i]-'a'];
   }
   root->isEndOfWord = true;
}

// Helper function to print the word found
void printWord(char* str, int n)
{
   cout<<endl;
   for(int i=0; i<n; i++)
   {
      cout<<str[i];
   }
}

// Print all words in Trie
void printAllWords(TrieNode* root, char* wordArray, int pos = 0)
{
   if(root == NULL)
      return;
   
   if(root->isEndOfWord)
   {
      printWord(wordArray, pos);
   }
   for(int i=0; i<NO_OF_ALPHABETS; i++)
   {
      if(root->child[i] != NULL)
      {
         wordArray[pos] = i+'a';
         printAllWords(root->child[i], wordArray, pos+1);
      }
   }
}

// Check if a word is present in the Trie or not
bool isValidWord(TrieNode* r, char* str)
{
   if(str == NULL )
      return true;
   if(*str == '\0')
      return r->isEndOfWord;
   
   if(r->child[*str - 'a'] == NULL)
      return false;
   else
      return isValidWord( r->child[*str - 'a'], str+1);
}

int main()
{
   TrieNode* root = new TrieNode;
   
   insert(root, "bad");
   insert(root, "bed");
   insert(root, "beard");
   insert(root, "beautiful");
   insert(root, "beauty");
   insert(root, "bread");
   
   char wordArray[MAX_WORD_SIZE];
   printAllWords(root, wordArray);
}

 

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)