> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-4/advanced_data_structures/text-data/trie.md).

# Prefix Tree

## Intro

We can consider trie as a space efficient hash table for words. It supports add(word) and contains(word) in O(len(word)) time. Trie saves space because it stores words with common prefixes under the same path.

## Implement Trie ([LC.208](https://leetcode.com/problems/implement-trie-prefix-tree/))

> Implement a trie with insert, search, and startsWith methods.
>
> * insert - Inserts a word into the trie
> * search - Returns if the word is in the trie
> * startsWith - Returns if there is any word in the trie that starts with the given prefix

## Example

```
Trie trie = new Trie();
trie.insert("lol");
if (trie.search(word)) freqMap.get(word)++;
if (trie.startsWith(prefix)) freqMap.get(prefix)++;
```

## Analysis

Trie is a n-ary tree depending on the number of available characters. Each node should hold its children map, (and its own key?), and isWord boolean. Internally, we want to store a dummyRoot to signify the empty string prefix.

## Code

```java
public class Trie {
    private class TrieNode {
        Map<Character, TrieNode> children;
        Boolean isWord;
        public TrieNode() {
            children = new HashMap<Character, TrieNode>();
            isWord = false;
        }
    }

    TrieNode dummyRoot;

    public Trie() {
        dummyRoot = new TrieNode();
    }

    /** 
     * Inserts a word into the trie. 
     */
    public void insert(String word) {
        TrieNode current = dummyRoot;
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (!current.children.containsKey(letter)) {
                current.children.put(letter, new TrieNode());
            }
            current = current.children.get(letter);
        }
        current.isWord = true;
    }

    /** 
     * Returns if the word is in the trie. 
     */
    public boolean search(String word) {
        return searchPrefix(word) != null && searchPrefix(word).isWord;
    }

    /** 
     * Returns if there is any word in the trie that starts with the given prefix. 
     */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    /**
     * Search the prefix tree for the word
     * @return the node that matches the last character in word, null if no match
     */
    private TrieNode searchPrefix(String word) {
        TrieNode travel = dummyRoot;
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (travel.children.containsKey(letter)) {
                travel = travel.children.get(letter);
            } else {
                return null;
            }
        }
        return travel;
    }
}
```

## Follow Up #1 ([LC.211](https://leetcode.com/problems/add-and-search-word-data-structure-design/description/))

The search query can contain `.` which matches any character.

## Example

```
addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true
```

## Analysis

Before, we use a travel pointer to travel down a path (just like traversing a linked list). Now, in order to support `.`, we need to explore an entire subtree to find a match. Preform a DFS on all the possible children at that level and then figure out one path that matches with the given word.

## Code

```java
/** 
 * Returns if the word is in the data structure. 
 * A word could contain the dot character '.' to represent any one letter. 
 */
public boolean search(String word) {
    return searchWord(word, dummyRoot, 0);
}

private boolean searchWord(String word, TrieNode curNode, int curIndex) {  
    // base case
    if (word.length() == curIndex) {    
        return curNode.isWord;
    }
    // search
    char curLetter = word.charAt(curIndex);
    if (curLetter == '.') {
        for (Character match : curNode.children.keySet()) {
            if (searchWord(word, curNode.children.get(match), curIndex + 1)) {
                return true;
            }
        }
    } else {
        if (curNode.children.containsKey(curLetter)) {
            return searchWord(word, curNode.children.get(curLetter), curIndex + 1);
        } else {
            return false;
        }
    }
    return false;
}
```

## Follow Up #2

The search query can contain `*` which can match 0 or more previous character.

## References

* UMD CS420 Lecture 23 [Tries & Suffix Trees](https://www.cs.umd.edu/class/spring2008/cmsc420/L23.SuffixTrees.pdf)
* Implement Trie [Editoral Solution](https://leetcode.com/articles/implement-trie-prefix-tree/)
* Wikipedia [Prefix Tree](https://en.wikipedia.org/wiki/Trie), [Compact Prefix Tree](https://en.wikipedia.org/wiki/Radix_tree)