Trie (not Tree)
A Trie is an exciting data structure but sadly not so famous. It’s used to store words compactly, space efficient for words starting with the same patterns, and time efficient for search terms with the same prefix (for example, searching a name in a lengthy phone book). It’s built like a tree/graph with letters as values; each node has up to 26 characters (for the English alphabet).
Trie (and not Tree), is a special Tree with up 26 children (in case of storing only English characters, could be more or less, depending on what you decide to store) as opposed as a Binary Tree which has at most 2 children
Let’s define what type of node we need for a Trie.
A Trie node is composed of a Character for the current value, a Boolean isWord indicating if the current character is the end of a complete word, and a list of children nodes.
Let’s add some helper functions.
This function will give the child node for the given character if it exists.
This function will create a new node if it doesn’t exist. In the case of an existing node, you should use the update function below.
This function will update the isWord property of the node.
Now let’s have a look at the Trie itself.
Like most trees, it requires only a root property. In the Trie case, we create it with an existing root with the empty character “\0” and false as it is not a valid word.
The Trie has two essential methods insert and search, let’s dive into them.
For each character, we get the child of the current node (we start from the root) and assign it to the current node; if it doesn’t exist, we create it and set it to the current node. We update the node’s isWord property for the word’s last character to true.
To find a word (not empty), we search from the root and iterate from all its characters; if one character is missing, we cannot find the word, then return false. For the last character, if isWord is true, we return true as it is a word; otherwise, we will end up returning false as we finished to iterate through all the characters.
Time Complexity:
- Insert: O(n), where n is the length of the given word,
- Search: O(n), where n is the length of the given word.
How to use the Trie:
<< AVL Tree | Book | Heap >>
