Search code examples
data-structurestrierecursive-datastructures

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

  • "bad"
  • "parent"

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

Solution

  • 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