Trie (Prefix Tree)
Overview
Trie (also known as Prefix Tree) is one of my favorite types of trees. It's very useful and is very easy to understand conceptually. It stores letters that build words. It's main use cases are in text field autocompletion, spell checking and some other cases that require searching by a prefix. In short - you are using it all the time when you type on the internet and get suggestion/autocompletion.
So let's now explain how exactly a Trie stores its data.
Root, nodes and leaf nodes - there 3 elements are very important in a Trie.
The root node is empty (as an empty string). Each other node contains a letter and the leaf nodes contain the full word that all the letters on the path to that leaf nodes has built.
I'm sure if you look at the animation, you'll understand it quickly but let's also explain it with the text field typing example too.
When we click on a text field - we see the cursor but we haven't typed anything yet - the value is an empty string. This corresponds to the Root node of a Trie - an empty value.
In this case, we can either show all possible paths (words) from the Trie or show nothing and wait for input (obviously waiting for input will be the more optimized option).
So then if we type 1 letter, we check if it matches a node that's connected to the Root and if so, we get 1 node deep in the tree (visualized in the end of the animation). With each typed letter that matches another connection, we go deeper in the tree until we match a leaf node (whole word) or stop getting matches and our input is no longer stored in the tree.
And for conclusion, the time complexity in Trie is as follows:
Insertion: O(n) - n is the length of the searched string
Search: O(n), for searching a string of length L.
Deletion: O(n), when removing a string of length L.
Autocomplete/Prefix Search: O(P + K), P is the prefix length and K is the number of strings with the given prefix
With these time complexities, a Trie is a very efficient choice for the use cases we already mentioned yet its performance may vary greatly due to how balanced it is (remember 'balance' from Red-black and AVL trees?) and how it is implemented. Also, a Trie may perform much better when used for a given language compared to other. For instance, the words in English are generally much shorter than words in German (or at least it seems so) so the shorter words, the better performance.
Also,
Code
class TrieNode:
def __init__(self):
self.children = {}
self.is_end_of_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end_of_word = True
def search(self, word):
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end_of_word
def starts_with(self, prefix):
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# Create a new Trie
trie = Trie()
# Insert words
trie.insert("git")
trie.insert("go")
trie.insert("root")
trie.insert("vim")
# Search for words
print(trie.search("git")) # True
print(trie.search("go")) # True
print(trie.search("root")) # True
print(trie.search("vim")) # True
print(trie.search("vscode")) # False
# Check prefixes
print(trie.starts_with("gi")) # True
print(trie.starts_with("roo")) # True
print(trie.starts_with("vi")) # True
print(trie.starts_with("goo")) # False
class TrieNode {
constructor() {
this.children = new Map();
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
insert(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) {
node.children.set(char, new TrieNode());
}
node = node.children.get(char);
}
node.isEndOfWord = true;
}
search(word) {
let node = this.root;
for (let char of word) {
if (!node.children.has(char)) {
return false;
}
node = node.children.get(char);
}
return node.isEndOfWord;
}
startsWith(prefix) {
let node = this.root;
for (let char of prefix) {
if (!node.children.has(char)) {
return false;
}
node = node.children.get(char);
}
return true;
}
}
// Create a new Trie
const trie = new Trie();
// Insert words
trie.insert("git");
trie.insert("go");
trie.insert("root");
trie.insert("vim");
// Search for words
console.log(trie.search("git")); // true
console.log(trie.search("go")); // true
console.log(trie.search("root")); // true
console.log(trie.search("vim")); // true
console.log(trie.search("vscode")); // false
// Check prefixes
console.log(trie.startsWith("gi")); // true
console.log(trie.startsWith("roo")); // true
console.log(trie.startsWith("vi")); // true
console.log(trie.startsWith("goo")); // false
import java.util.HashMap;
import java.util.Map;
class TrieNode {
Map<Character, TrieNode> children;
boolean isEndOfWord;
TrieNode() {
children = new HashMap<>();
isEndOfWord = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
public void insert(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
node.children.putIfAbsent(ch, new TrieNode());
node = node.children.get(ch);
}
node.isEndOfWord = true;
}
public boolean search(String word) {
TrieNode node = root;
for (char ch : word.toCharArray()) {
if (!node.children.containsKey(ch)) {
return false;
}
node = node.children.get(ch);
}
return node.isEndOfWord;
}
public boolean startsWith(String prefix) {
TrieNode node = root;
for (char ch : prefix.toCharArray()) {
if (!node.children.containsKey(ch)) {
return false;
}
node = node.children.get(ch);
}
return true;
}
public static void main(String[] args) {
Trie trie = new Trie();
// Insert words
trie.insert("git");
trie.insert("go");
trie.insert("root");
trie.insert("vim");
// Search for words
System.out.println(trie.search("git")); // true
System.out.println(trie.search("go")); // true
System.out.println(trie.search("root")); // true
System.out.println(trie.search("vim")); // true
System.out.println(trie.search("vscode")); // false
// Check prefixes
System.out.println(trie.startsWith("gi")); // true
System.out.println(trie.startsWith("roo")); // true
System.out.println(trie.startsWith("vi")); // true
System.out.println(trie.startsWith("goo")); // false
}
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define ALPHABET_SIZE 26
struct TrieNode {
struct TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
};
struct Trie {
struct TrieNode* root;
};
struct TrieNode* createNode() {
struct TrieNode* node = (struct TrieNode*)malloc(sizeof(struct TrieNode));
node->isEndOfWord = false;
for (int i = 0; i < ALPHABET_SIZE; i++) {
node->children[i] = NULL;
}
return node;
}
struct Trie* createTrie() {
struct Trie* trie = (struct Trie*)malloc(sizeof(struct Trie));
trie->root = createNode();
return trie;
}
void insert(struct Trie* trie, const char* word) {
struct TrieNode* node = trie->root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (!node->children[index]) {
node->children[index] = createNode();
}
node = node->children[index];
}
node->isEndOfWord = true;
}
bool search(struct Trie* trie, const char* word) {
struct TrieNode* node = trie->root;
for (int i = 0; word[i]; i++) {
int index = word[i] - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return node->isEndOfWord;
}
bool startsWith(struct Trie* trie, const char* prefix) {
struct TrieNode* node = trie->root;
for (int i = 0; prefix[i]; i++) {
int index = prefix[i] - 'a';
if (!node->children[index]) {
return false;
}
node = node->children[index];
}
return true;
}
int main() {
struct Trie* trie = createTrie();
// Insert words
insert(trie, "git");
insert(trie, "go");
insert(trie, "root");
insert(trie, "vim");
// Search for words
printf("%d\n", search(trie, "git")); // 1 (true)
printf("%d\n", search(trie, "go")); // 1 (true)
printf("%d\n", search(trie, "root")); // 1 (true)
printf("%d\n", search(trie, "vim")); // 1 (true)
printf("%d\n", search(trie, "vscode")); // 0 (false)
// Check prefixes
printf("%d\n", startsWith(trie, "gi")); // 1 (true)
printf("%d\n", startsWith(trie, "roo")); // 1 (true)
printf("%d\n", startsWith(trie, "vi")); // 1 (true)
printf("%d\n", startsWith(trie, "goo")); // 0 (false)
return 0;
}
<?php
class TrieNode {
public $children = [];
public $isEndOfWord = false;
}
class Trie {
private $root;
public function __construct() {
$this->root = new TrieNode();
}
public function insert($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = $word[$i];
if (!isset($node->children[$char])) {
$node->children[$char] = new TrieNode();
}
$node = $node->children[$char];
}
$node->isEndOfWord = true;
}
public function search($word) {
$node = $this->root;
for ($i = 0; $i < strlen($word); $i++) {
$char = $word[$i];
if (!isset($node->children[$char])) {
return false;
}
$node = $node->children[$char];
}
return $node->isEndOfWord;
}
public function startsWith($prefix) {
$node = $this->root;
for ($i = 0; $i < strlen($prefix); $i++) {
$char = $prefix[$i];
if (!isset($node->children[$char])) {
return false;
}
$node = $node->children[$char];
}
return true;
}
}
// Create a new Trie
$trie = new Trie();
// Insert words
$trie->insert("git");
$trie->insert("go");
$trie->insert("root");
$trie->insert("vim");
// Search for words
echo $trie->search("git") . "\n"; // 1 (true)
echo $trie->search("go") . "\n"; // 1 (true)
echo $trie->search("root") . "\n"; // 1 (true)
echo $trie->search("vim") . "\n"; // 1 (true)
echo $trie->search("vscode") . "\n"; // 0 (false)
// Check prefixes
echo $trie->startsWith("gi") . "\n"; // 1 (true)
echo $trie->startsWith("roo") . "\n"; // 1 (true)
echo $trie->startsWith("vi") . "\n"; // 1 (true)
echo $trie->startsWith("goo") . "\n"; // 0 (false)