Trie Tree

It is a search tree.

• insert, delete, or search for some kind of "keys"
• store ordered data

What is the requirement of this dictionary?

• n - # of words
• m - average length of the string/word

• k - # of words with the same prefix

• search (word)

• delete
• add
• find all words with given prefix, e.g., auto-completion in google search
  • in HashMap O(nm)

!trie tree

Implementation

class TrieNode {
    Map<Character, TrieNode> children;
    // another way: TrieNode[] children; // size 26 array
    Integer value;
    boolean isWord;
}