design a tree structure which generates dynamic substrees

[dongfei]

There is an interview question I am asked in Microsoft. Write a
function to build a word tree from a dictionary ?

Input: a dictionary file
Function: void build(filename);
the sample.
Root--a----t
| |__
|___ bout
by

At first, I design it using a trie tree that every tier contains 26
letters.
struct trienode
{
trienode* subtree[26];
char* ch;
};

But the interviewer said it wastes a lot space. I only need to insert
the nodes if necessary. How to design the data structure to support
the dynamic allocated nodes?

[red floyd]

You should learn about the associative containers in the Standard Library.

[Kai-Uwe Bux]

dongfei wrote:

See Knuth: TAOCP, Vol 3, 6.3 (digital searching).

The main idea is a space-time tradeoff. You can do

struct trienode {
char* str;
trienode* next;
trienode* down;
};

and use a linked list for the siblings of a node.

Best

Kai-Uwe Bux

[dongfei]

Thanks, could you implement the function of build(filename) ?

[Kai-Uwe Bux]

dongfei wrote:

Sure.

Apart from IO checking, the function would roughly look like this:

trienode* build ( std::string const & filename ) {
trienode * root = 0;
std::ifstream dictionary ( filename.c_str() );
std::string word;
while ( dictionary >> word ) {
insert( root, word );
}
return ( root );
}

The insert function would have the signature:

void insert ( trienode* & root, std::string word );

and implementing it is left as an exercise.

Best

Kai-Uwe Bux