struct State {
const TrieNode* data;
string acc;
int index;
State( ... ): ... {} // element-wise constructor, left as an exercise
};
std::vector<string> getWords( const TrieNode* root )
{
std::vector<string> retval;
std::vector<State> states;
states.push_back( State( root, string(), 0 ) );
while (!states.empty())
{
State s = states.back();
states.pop_back();
if (s.data->eow)
{
retval.push_back( s.acc );
continue;
}
if (s.index >= 26)
continue;
states.push_back( State( s.data, s.acc, s.index+1 ) );
if (s.letters[s.index])
{
states.push_back( State( s.letters[s.index], s.acc + s.letters[s.index]->letter, 0 ) );
}
}
return std::move(retval);
};
The states is an explicit stack that tracks the same data as you tracked recursively, pretty much. I think I managed to visit the elements in the same order your recursive function would, but that wouldn't really matter.
Note that the above code is written and not tested, and you have to write an element-wise constructor for State, because I'm lazy.