CODEWITHSUNDEEP
javadata-structurestrie
Maksim Dmitriev
Maksim Dmitriev

Reputation: 6209

Array-based Trie Implementation. Non-null value in the child array

I'm trying to understand the array-based implementation of Trie from http://www.programcreek.com/2014/05/leetcode-implement-trie-prefix-tree-java/ (see Java Solution 2 - Improve Performance by Using an Array).

public void insert(String word) {
    TrieNode p = root;
    for(int i = 0; i < word.length(); i++) {
        char c = word.charAt(i);
        int index = c - 'a';
        if(p.arr[index] == null) {
            TrieNode temp = new TrieNode();
            p.arr[index] = temp;
            p = temp;
        } else {
            p = p.arr[index];
        }
    }
    p.isEnd = true;
}

I'm not sure the else branch is ever executed. What am I missing?

Update 1

The given word only contains lower-case English letters

Upvotes: 0

Views: 511

Answers (2)

DPenner1
DPenner1

Reputation: 10462

The first time you call this function, the else branch will indeed not execute. However, as the Trie gets populated, it is very possible that p.arr[index] is not null.

For example, calling insert("i") will cause add a new TrieNode at root.arr['i' - 'a']. Calling the function a second time, for example with insert("it"), will result in the check p.arr[index] == null returning false because the first insert already added the TrieNode for i at the root node.

You can test this out with the following main function (and putting a breakpoint or println statement in the else branch)

public static void main (String[] args)
{
    Trie t = new Trie();
    t.insert("i");
    t.insert("it");
}

Upvotes: 2

Serg M Ten
Serg M Ten

Reputation: 5606

That looks to me pretty much like a bug. If c-'a'>26 then p.arr[index] won't be null but will raise an ArrayIndexOutOfBounds exception.

Upvotes: 1

Related Questions