Primitive values (int) in Tries while doing DFS

Question

I m trying to calculate the value of prefixCount in Trie, as below.

I am puzzled why the value of count is not returned as 3

Just in case , Tries contains [by,bye, byer, rat]. Why count is return as 0, and not 3.

public int prefixCount(String prefix)
{
    int count = 0;
    TrieNode node = searchPrefix(prefix);
    if(node != null)
    {
        prefixCount(prefix, node, count);
    }
    return count;
}

public void prefixCount(String prefix, TrieNode node, int count)
{
    if(node.isEnd())
    {
        count++;
    }

    for(int index = 0;index < 26;index++)
    {
        char value = (char) (index + 'a');
        TrieNode next = node.get(value);
        if(next != null)
        {
            prefixCount(prefix + value, next, count);
        }
    }
}

Am i doing something wrong while doing DFS operation.

Thanks !

One method assigns count to be 0 and never updates its value, so it returns 0. The other methods doesn't return anything. — azurefrog, Jan 26 '18 at 16:25
Yes , I think wasn't thinking in that manner. I was able to correct my method defination — user1993412, Jan 26 '18 at 16:35

score 0 · Accepted Answer · answered Jan 26 '18 at 16:37

I was not defining my method correctly. The appropriate method would be as below.

public int prefixCount(String prefix)
{
    int count = 0;
    TrieNode node = searchPrefix(prefix);
    if(node.isEnd())
    {
        count++;
    }

    for(int index = 0;index < 26;index++)
    {
        char value = (char) (index + 'a');
        TrieNode next = node.get(value);
        if(next != null)
        {
            count += prefixCount(prefix + value);
        }
    }
    return count;
}

Thanks !

Primitive values (int) in Tries while doing DFS

1 Answers1