use trie data structure to solve the problem of clustering anagrams Given an array of words, print all anagrams together. For example, if
  the given array is {“cat”, “dog”, “tac”, “god”, “act”}, then output
  may be “cat tac act dog god”.


The following is my c++ code. I use raw pointer to implement varying number of children
for practice. Actually, I guess maybe it's better to adopt STL containers. 

#include &lt;iostream&gt;
#include &lt;cstring&gt;
using namespace std;

struct Index_node_base
{
    Index_node_base* next;
    Index_node_base():next(NULL){}  
};

struct Index_node : public Index_node_base
{
    int index;
    Index_node(int i):index(i), Index_node_base(){}
};

void insert_index_node(Index_node** head, int i)
{
    Index_node* node = new Index_node(i);
    node-&gt;next = (*head);
    *head = node;
}

struct Trie_node_base
{
    typedef Trie_node_base* Base_ptr;

    Base_ptr* child;
    int num_of_child;

    Trie_node_base(int n)
    {
        child = new Base_ptr[n];
        for(int i=0; i &lt; n; ++i)
            child[i] = NULL;
        num_of_child = n;
    }

    ~Trie_node_base()
    {
        delete [] child;
    }
};

struct Trie_node : public Trie_node_base
{
    bool is_end;
    Index_node* head;
    Trie_node(int n):Trie_node_base(n), is_end(false), head(NULL){}
};

class Trie
{
public:
    Trie(int n=26)
    {
        root = new Trie_node(n);
    }
    ~Trie()
    {
        destroy(root);
    }

    void insert_trie_node(const char* w, int ind);
    Trie_node* get_root_node();

private:
    Trie_node* root;
    void destroy(Trie_node* root);
};

Trie_node* Trie::get_root_node()
{
    return root;
}

void Trie::insert_trie_node(const char* w, int ind)
{
    Trie_node* r = root;
    while(*w)
    {
        int i = *w - 'a';
        if(r-&gt;child[i] == NULL)
        {
            r-&gt;child[i] = new Trie_node(r-&gt;num_of_child);
        }
        r = (Trie_node*)r-&gt;child[i];
        ++w;
    }

    if(r-&gt;is_end)
    {
        insert_index_node(&amp;(r-&gt;head), ind);
    }
    else
    {
        r-&gt;is_end = true;
        r-&gt;head = new Index_node(ind);
    }
}

void traversal_trie(const char* word_arr[], Trie_node* r)
{
    size_t i;

    if(r-&gt;is_end)
    {        
        Index_node* h = r-&gt;head;
        while(h != NULL)
        {
            printf("%s\n", word_arr[h-&gt;index]);
            h = (Index_node*)h-&gt;next;
        }
    }


    for(i = 0; i &lt; r-&gt;num_of_child; ++i)
    {
        if(r-&gt;child[i] != NULL)
            traversal_trie(word_arr, (Trie_node*)r-&gt;child[i]);
    }    
}

void Trie::destroy(Trie_node* root)
{
    size_t i;

    for(i = 0; i &lt; root-&gt;num_of_child; ++i)
    {
        if(root-&gt;child[i] != NULL)
            destroy((Trie_node*)root-&gt;child[i]);
    }

    if(root-&gt;is_end)
    {
        Index_node* h = root-&gt;head;
        Index_node* tmp = NULL;

        while(h != NULL)
        {
            tmp = (Index_node*)h-&gt;next;
            delete h;
            h = tmp;
        }        
    }

    delete root;
}

static int comp_char(const void* x, const void* y)
{
    const char* c1 = (const char*)x;
    const char* c2 = (const char*)y;

    return *(c1) - *(c2);
}

static void cluster_anagrams(const char* word_arr[], size_t size)
{
    Trie* trie = new Trie(26);
    size_t i;
    char* buffer;

    for(i = 0; i &lt; size; ++i)
    {
        int len = strlen(word_arr[i]);
        buffer = new char [len+1];
        memcpy(buffer, word_arr[i], len+1);        
        qsort(buffer, strlen(buffer), 1, comp_char);   
        trie-&gt;insert_trie_node(buffer, i);          
        delete buffer;
    }

    cout &lt;&lt; "Debug!" &lt;&lt; endl;
    traversal_trie(word_arr, trie-&gt;get_root_node());
}

int main()
{
    const char* word_arr[] = {"cat", "dog", "tac", "god", "act", "gdo"};
    size_t size = sizeof(word_arr) / sizeof(word_arr[0]);
    cluster_anagrams(word_arr, size);    

    system("pause");
    return 0;
}
#include &lt;cstring&gt;


Avoid including C headers when programming C++.

struct Index_node_base
{
    Index_node_base* next;
    Index_node_base():next(NULL){}  
};

struct Index_node : public Index_node_base
{
    int index;
    Index_node(int i):index(i), Index_node_base(){}
};

void insert_index_node(Index_node** head, int i)
{
     Index_node* node = new Index_node(i);
     node-&gt;next = (*head);
     *head = node;
}


This is overkill as you are just re-implementing a list of numbers / characters.

const char*


This is C code, consider using the C++ std::string instead.

const char* word_arr[]


For example, this one should be a std::list&lt;std::string&gt; (a.k.a. list&lt;string&gt;)

 printf("%s\n", word_arr[h-&gt;index]);


Again C, use the C++ iostreams instead. This should be like cout &lt;&lt; ... &lt;&lt; endl;

while(*w)
{
    int i = *w - 'a';
    if(r-&gt;child[i] == NULL)
    {
        r-&gt;child[i] = new Trie_node(r-&gt;num_of_child);
    }
    r = (Trie_node*)r-&gt;child[i];
    ++w;
}


You can use iterators and STL algorithms to do this in one line.

for(i = 0; i &lt; r-&gt;num_of_child; ++i)
{
    if(r-&gt;child[i] != NULL)
        traversal_trie(word_arr, (Trie_node*)r-&gt;child[i]);
}


This would also be one line using for_each on iterators and passing traversal_trie.

void Trie::destroy(Trie_node* root)


You won't need destory anymore as a result; also, there's a chance you might not need pointers.

static int comp_char(const void* x, const void* y)
{
    const char* c1 = (const char*)x;
    const char* c2 = (const char*)y;

    return *(c1) - *(c2);
}


This is messsy, you are doing useless C style voids and casts and not using C++ overloading. This body would have been something along the line of just the line return c1 &lt; c2;

for(i = 0; i &lt; size; ++i)
{
    int len = strlen(word_arr[i]);
    buffer = new char [len+1];
    memcpy(buffer, word_arr[i], len+1);        
    qsort(buffer, strlen(buffer), 1, comp_char);   
    trie-&gt;insert_trie_node(buffer, i);          
    delete buffer;
}


memcpy? Not necessary, std::string allows you to copy the string and not mess with memory.