Intro

Trie is a tree-like data structure for storing sequences of tokens (characters, permutations of digits or shapes, etc.) where:

• root node value is empty (empty prefix “”)
• each edge is labeled with a token
• each node represents the prefix spelled by the path from root to that node, and has:
  • value a token
  • has children (commonly a dictionary in Python, a fixed array in other languages with the size of the alphabet)
  • end marker (boolean is_end) to mark that a complete word ends here

Bitwise Trie uses individual bits from fixed-length binary data, such as integers or memory addresses, as keys

Usage

• autocomplete/prefix searching & storing
• spell checking
• Longest Prefix Matching Algorithm (Maximum Prefix Length Match) in IP routing

Comparison

• nodes in a Trie, unlike a BST, do not store their associated key; instead, each node's position within the trie determines its associated key, with the connections between nodes defined by individual characters rather than the entire key

Advantages

• sometimes space efficient (if storing lots of words with similar prefixes, overall storage cost is reduced because it stores shared prefixes only once)
• efficient prefix queries/searches (e.g., How many words start with "choco"?, What's the most likely next letter in a word that starts with "unbo"?)
• within a trie, keys can be efficiently sorted lexicographically
• sometimes preprocessing a dictionary of words (given in a list) into a trie, will improve the efficiency of searching for a word of length k, among n words ⇒ searching becomes O(k) instead of O(n)

Disadvantages

• usually space inefficient (rarely save space when compared to storing strings in a set)

  • ASCII characters in a string = 1 byte each

    link between trie nodes = pointer to an address = 8 bytes on a 64-bit system

    ⇒ the overhead of linking nodes together often outweighs the savings from storing fewer characters

• not standard, has to be implemented manually

Problems

• [ ] Implement Trie (Prefix Tree)
• [ ] Add and Search Word
• [ ] Word Break
• [ ] Word Break II
• [ ] Word Search II
• [ ] Unique rows in a binary matrix
• [ ] Count of distinct substrings
• [ ] Word Boggle
• [ ] Maximum XOR of Two Numbers in an Array
• [ ] Replace Words
• [ ] Implement Magic Dictionary
• [ ] Map Sum Pairs
• [ ] Longest Word in Dictionary
• [ ] Top K Frequent Words
• [ ] Prefix and Suffix Search

Corner Cases

• a word is also a prefix to itself
• a word can end at a node that still has children
• searching in an empty trie
• inserting empty strings

Implementation

Trie

insert(word)

remove(word)

isPrefix() - returns true if any word in the Trie begins with the given prefix

isWord(word) - returns true if the given word is present in the Trie

getWordWithPrefix(prefix) - return any word in the Trie that begins with the given prefix

getWordsWithPrefix(prefix) - return all words in the Trie that begin with the given prefix

getTotalWordsWithPrefix(prefix) - return the number of words in the Trie that begin with given prefix

getTotalWords() - return the number of words in the Trie

l is the length of the longest string in the Trie

m is the length of the average string used in the operation

n is the number of words in the Trie

alphabet_size

Algorithms

Patterns

Code

Resources

Trying to Understand Tries

Insert

void insert(String key)

Function to insert a key in the trie.

Inserts the string key into the trie.

Every character of the input key is inserted as an individual Trie node.

Note that the children is an array of pointers (or references) to next level trie nodes. The key character acts as an index to the array children.

If the input key is new or an extension of the existing key, we need to construct non-existing nodes of the key, and mark the end of the word for the last node.

If the input key is a prefix of the existing key in Trie, we simply mark the last node of the key as the end of a word.

The key length determines Trie depth.

Remove

void remove(String key)

Function to delete a key in the trie.

During delete operation we delete the key in bottom-up manner using recursion. The following are possible conditions when deleting key from trie:

1. Key may not be there in trie. Delete operation should not modify trie.
2. Key present as unique key (no part of key contains another key (prefix), nor the key itself is prefix of another key in trie). Delete all the nodes.