Search code examples
javatrielevels

Height of a trie (number of levels)

I have a trie where each node is an object TrieNode like this:

public char content; 
public double count;
public LinkedList<TrieNode> childList;

I had to count the height of the trie (root had level = 0).

So this is what I've done:

int levels = getLevels(getRoot());
System.out.println("levels: " + levels);

public int getLevels(TrieNode node) {
    int lev = 0;
    if(node != null) {
        TrieNode current = node;  
        for(TrieNode child : node.childList) {
            lev += getLevels(child);
        }      
    }   
    return lev;
}

But it returns always 0. Why? Thanks

Solution

  • You need to add 1 when you descend to children, otherwise nothing gives lev a non-zero value.

    Note that you're not calculating the height of the trie in this code, you're summing the lengths of the paths. You need to find the maximum path length:

    int lev = 1;
for (TrieNode child : node.childList) {
  lev = Math.max(lev, 1 + getLevels(child));
}