How to find the height of a trie tree in C

Question

I'm having trouble to write the algorithm to find the height of a trie tree. I have no ideia how to start off or how I can possibly do it. Sorry if this is a 'noob' question, but I'm pretty new to tries and this is the only part missing for my assignment.

Anyway here is the structure of the trie tree:

typedef struct RegTrie * ImplTrie;
typedef struct RegTrie {
  Boolean IsItAWord; /* true if it is a word, false if it is not a word */
  ImplTrie children[ALPHABETsize];
} RegTrie;

So basically, if 'a' is one child, there will be a Trie in chidren[0], and if 'b' is not a child, children[1] will be NULL. As you can see the characters are implicitly defined by the link index, and if the characters of the past nodes form a word up until the current node, 'Boolean IsItAWord' will be true.

Could you guys give me a light in this? The only thing I know is that the height can be defined by the lenght of the longest word + 1. But I don't know how to do that. I really just want a solution, so any methods to find the height of this trie will be greatly appreciated.

Thank you.

Answer 1

You can do it with a recursive function that takes ImplTrie and returns an int.

The base case checks if ImplTrie is NULL, in which case the function returns 0.

Otherwise, the function walks in a loop through children, calls itself, picks the max value, and returns the max value plus one.

int height(ImplTrie t) {
    if (!t) return 0;
    int res = 0;
    for (int i = 0 ; i != ALPHABETsize ; i++) {
        int h = height(t->children[i]);
        if (h > res) {
            res = h;
        }
    }
    return res + 1;
}