Trie

reTRIEval

TRIE storing dictionary, will use word structure
- Not every node contains words
- Nodes can have > 2 children
- Have internal nodes that does not represent any word.

Performance vs. BST:
1. find a key:
BST: O(logn)
Trie: slightly better (since most words are not long)

Use a hashmap to store the link to the next node in trie because:
1. Use ArrayList waste a lot of space
2. Use linkedList will lose the index of some particular character.
https://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html
HashMap<Character, TrieNode> Children;
put(key, value);
get(key);

Application:
A. Autocomplete: ex. autocomplete "ea"
    1. Find the stem
    2. Do a level traversal from there (if want to generate words from shortest to longest)