CODEWITHSUNDEEP
data-structurestrierecursive-datastructures
user1422163
user1422163

Reputation: 135

Trie Data Structure : How tp prevent false positives when searching a word?

class Node{  
 Map<Character,Node> childMap = new HashMap<>();
 boolean isWord;
}

A trie data node is usually represnted as the above class. Let's assume that we inserted

into the trie.
If the trie is searched for "pad" in the trie, wouldn't it return a "true" which is wrong?

Upvotes: 0

Views: 100

Answers (2)

dnickless
dnickless

Reputation: 10918

Not quite. A Trie is generally implemented using a recursive structure (a composite pattern) as you correctly pointed out. However that's precisely what would stop it from returning true for "pad" since after the insert of "parent" the structure would look like

root
    b
        a
            d
    p
        a
            r
                e
                    n
                        t

So following down the Trie, anything that starts with "p" will never and on "d".

There often is another challenge in Trie implementations, though, which requires one last step to find out if you've actually found a complete word or just a prefix. And that's precisely what the isWord variable is for in your example. So after iterating down the nodes you got to test that property.

Upvotes: 0

user31264
user31264

Reputation: 6727

No, it wouldn't return true. If it does, either there is a bug in your code, or you don't understand the concept of trie.

If you inserted "bad" and "parent", the trie would look like this:

(root)->b->a->d
  |  
  +---->p->a->r->e->n->t

"pad" would not be found

Upvotes: 1

Related Questions