If you're not familiar with tries and want to learn more, then this post is for you! A trie is like pie in that both rhyme* but that’s where the similarities end. A trie is a tree-like data structure used to efficiently store a set of strings. It’s also commonly referred to as a prefix tree or digital tree.
*and it’s a helpful mnemonic since I initially pronounced trie like ‘tree’. Fun fact- trie was coined by Edward Fredkin who pronounced it like 'tree' as in 're-trie-val', but others have since pronounced it as 'try' to distinguish it from 'tree'.
How a Trie Works
A trie is known as a prefix tree because it builds a path from the root of the tree to any node that represents a prefix for at least one string in the set.
The root is associated with an empty string, and all of the descendants of a node will have a common prefix of the string associated with that node. The final leaf in the path acts as a terminal node and results in a complete word (a word recognized by the trie must begin at the root and end at a terminal node).
Below is a trie visualized with the darker shade representing a terminal node/completed word.
When to Use a Trie
It’s useful to use a trie if you have a dictionary of words and you want an efficient insert and lookup to see if a word exists in the dictionary (i.e. a spellcheck or predictive text program).
Big O Time and Space Complexity
The worst case time complexity for both inserting and searching is O(m) where m is the length of the word. Complexity depends on how long the given word is and not the number of words stored in the trie, as we will only be traveling a single path from root to terminal node.
The space complexity for a trie will depend on how often prefixes are shared among words. The guaranteed worst case is O(m * n) where m is the length of the word and n is the number of words.
Implementing a Trie
We can implement a trie by creating both a Trie and Node class.
Node Class
The Node class will not store values within the nodes of a trie, which is different than other tree structures. Instead, we will store values for each edge that leaves a node. Since a trie is not a binary tree, it can have any number of children, which will be stored in an Object.
The isTerminal property will keep track of whether the node represents a terminal node. Remember, a word is only recognized by the trie if it begins at the root and ends at a terminal node (last leaf in the path).
class Node {
constructor() {
this.children = {};
this.isTerminal = false;
}
}
Trie Class
For a basic Trie class implementation, we'll include insert() and search() functions.
insert()
When inserting a word into the Trie, we'll need to check if the first character of the word already exists as an edge. If the edge exists, then we'll want to use it to add our existing word. If the edge does not exist, then we'll need to create the edge. The method below takes a recursive approach to add the new destination node along with the remaining characters.
class Trie {
constructor() {
this.root = new Node();
}
insert(word, root = this.root) {
let char = word[0];
// if current root has no edge for the char, then we create a
// new edge for char and point it to a new destination node
if (!root.children[char]) {
root.children[char] = new Node();
}
// if there are no more remaining chars in word, we can
// mark the destination node's terminal property as true
if (word.length === 1) {
root.children[char].isTerminal = true;
// otherwise, recursively insert the remaining chars
// into destination nodes
} else {
this.insert(word.slice(1), root.children[char]);
}
}
}
search()
The search() function will tell us whether a word is recognized by the trie. This happens with a traversal down the tree. We start at the root and continually travel through the edges that correspond to the front character of the string.
The word is recognized by the trie if we traverse down to a terminal node and the string is empty. A word would not be recognized by the trie if the string is empty and we end up on a non-terminal node or if there is a character without an associated edge.
// ...
search(word, root = this.root) {
// if we've gone through all the characters in word
if (word.length === 0) {
// word exists if the current node is a terminal node
if (root.isTerminal) {
return true;
} else {
return false;
}
// taking the first character of the string
let char = word[0];
// if an edge exists for this char, then recursively check the
// subtree at the edge's destination with the remaining chars
if (root.children[char]) {
return this.search(word.slice(1), root.children[letter]);
} else {
return false;
}
}
The full code implementation is:
Tries may not seem like a super useful or common data structure but they are great for dictionary and word lookup problems. Also, tries can come up in interviews so it's good to get familiar with it. Happy coding and do enjoy some pie with your trie learning!
Resources
Trie - Interview Cake
Trie - Wikipedia
Tries - App Academy
Implement Trie (Prefix Tree) - Leetcode
Top comments (1)
Tries are even useful for range queries and to store other stuff despite Strings, see for instance Adaptive Radix Trie and HOT :-) so, it's now sometimes used in database systems instead of B-trees for instance because of the good asymptotic bounds for large datasets and the easy insertion operation.