Implementation of Trie data structure accommodating varying number of children

I've used the Trie data structure to solve the following problem:


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++ implementation which can accommodate varying number of children.

```
#include
#include
#include
#include
#include
using namespace std;

struct Trie_node_base
{
vector child;
int num_of_child;

Trie_node_base(int n)
{
num_of_child = n;
for(int i = 0; i ::const_iterator> head;

Trie_node(int num):Trie_node_base(num), is_word(false){}
};

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

void insert_trie_node(const string& w, vector::const_iterator ind);
Trie_node* get_root_node()
{
return root;
}

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

void Trie::insert_trie_node(const string& w, vector::const_iterator ind)
{
Trie_node* r = root;

string::const_iterator runner = w.begin();
for(; runner!=w.end(); ++runner)
{
char cur_char = *runner;
int i = cur_char - 'a';

if(r->child[i] == NULL)
{
r->child[i] = new Trie_node(r->num_of_child);
}
r = (Trie_node*)r->child[i];
}

if(!r->is_word)
r->is_word = true;
r->head.push_back(ind);
}

void Trie::destroy(Trie_node* root)
{
vector::iterator it = (root->child).begin();

for(; it != (root->child).end(); ++it)
{
if(*it != NULL)
destroy((Trie_node)(it));
}

delete root;
}

void traversal_trie(const vector& word_arr, Trie_node* r)
{
size_t i;

if(r->is_word)
{
vector::const_iterator>::iterator it = (r->head).begin();
for(; it != (r->head).end(); ++it)
{
cout num_of_child; ++i)
{
if(r->chil

Your code does several things more complex than required. In no particular order:

• What purpose does Trie_node_base serve? You don’t need a base class here since you only inherit from it once.

• Worse, your base class doesn’t have a virtual destructor.

-
To create an array of size n, you use a loop and push_back. Much easier would be to use the proper initialiser:

Trie_node_base(int n) :
    num_of_child(n) ,
    child(n)
    { }

-
In fact, you generally fail to use initialisers, and instead re-assign values inside the constructor.

• Consider proper naming. In the above code snippet, it should really be number_of_children and children (plural!).

• The num_of_child member is redundant – the same information is stored in the vector.

• The tree node root doesn’t need to, and shouldn’t be, a pointer.

• In general, your use of pointers and manual memory management makes the code vastly more complex and brittle (and requires the existence of the destroy method). If you need to use pointers, use smart pointers (std::unique_ptr in this case).

-
Better yet, omit pointers entirely. They are utterly unnecessary here. Unfortunately though, you cannot use std::vector with an incomplete class (the standard screwed up here). But you can (and should!) use boost::container::vector. Thus your tree node implementation becomes:

struct Trie_node
{
    boost::container::vector children;
    bool is_word;

    Trie_node(int n)
        : children(n)
        , is_word(false)
    { }
};

… There’s more but these are the essential points that will help reduce code complexity.

StackExchange Code Review Q#18785, answer score: 10