How to recursivly find the height of a Trie Tree

Question

I'm having a little trouble figuring out how to find the height of a trie tree data structure. I know for an AVL tree a simple recursive height function would be:

height(nodeType *node) const
{
  if(node == NULL)
    return 0;

  // if tree is not empty height is 1 + max of either path
  return 1 + std::max(height(node->left), height(node->right));
}

but now my trie tree has a children with 26 different indexes, there must be a simple way to find the maximum height without typing out all 26 different possible indexes. How could I go about this?

int height(trieNodeType *node) const
{
  if(node == NULL)
    return 0;

  for(int i = 0; i < 26; i ++) {
    //has to be something to do with a for loop, 
    //i know that much
  }
} 

Answer 1

Looping is the way to go.

C++11:

if (node == nullptr) return 0;

auto i = std::begin(node->children);
auto end = std::end(node->children);

auto max_height = height(i++);

while (i != end) {
    max_height = std::max(max_height, height(i++));
}

return 1 + max_height;

C++ <11.

if (node == NULL) return 0;

trieNodeType ** i = node->children;
trieNodeType ** end = i + (sizeof(node->children) / sizeof(trieNodeType *));

int max_height = height(i++);

while (i != end) {
    max_height = std::max(max_height, height(i++));
}

return 1 + max_height;