A trie is a tree-like data structure that can store multiple strings. A node in a trie stores a character. After building a trie, strings or substrings can be retrieved by traversing down a path (a branch) of the trie. Tries are used to find substrings, autocomplete, and many other string operations.
Each trie node might have multiple branches. So a trie node has a data structure to store the references to the next nodes in the branches. This data structure can be an array, a linked list, or a hash map. Using an array is the most intuitive implementation. This post is to introduce trie implementation using an array for the references to the next nodes.
Table of Content
- Map of trie implementations
- Define classes
- Insert a string
- Delete a string
- Search a string
- Print all strings in a trie
- Free download
Map of trie implementations
Part 1 – Trie implementation using an array.
Part 2 – Trie implementation using a linked list
Part 3 – Trie implementation using a hash map
Define classes in trie implementation
Like building a tree, we define a TrieNode class before a Trie class. A TrieNode class has three variables: data, children, and isEnd. data stores a character. children is a data structure that stores the references to the next nodes in the branches. The data structure is an array. If we use only the alphabet a-z, the length of the array is 26. If the string has special symbols or characters, the array length is 128 or 256. isEnd is to mark whether this is the last node in this branch, i.e. the last character in the string.
In the Trie class, there is a variable root. The operation of insertion, search, or deletion always starts from root. The data of the root can be any character, which is not associated with any strings. Its children hold references to the first characters in strings.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | import java.util.*; public class TrieArray { //don't use 26 if there is space or any other special characters static final int NUM_OF_CHARS = 128; class TrieNode { char data; TrieNode[] children = new TrieNode[NUM_OF_CHARS]; boolean isEnd; //Constructor, Time O(1), Space O(1) TrieNode(char c) { data = c; } } TrieNode root = new TrieNode(' '); |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.children = []; //array this.isEnd = false; } } class Trie { //Constructor, Time O(1), Space O(1) constructor() { this.root = new TrieNode(''); } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 | class TrieNode: #Constructor, Time O(1), Space O(1), 128 is constant def __init__(self, c): self.children = [None]*128 #don't use 26 if there is space or other special characters self.isEnd = False self.data = c class Trie: #Constructor, Time O(1), Space O(1) def __init__(self): self.root = TrieNode('') |
Insert a string in trie implementation
To insert a string, you start at root. For each character in the string, create a new node with the character as its data. Use the character as the index to find the cell in the array of children, and save the reference of the new node in that cell. Then move on to the newly created node. Once reaching the last character in the string, mark the node’s isEnd to be true.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Inserts a word into the trie, Iteration, Time O(s), Space O(s), s is word length void insert(String word) { if (search(word) == true) { System.out.println(word + " is already in trie."); return; } TrieNode node = root; for (char ch: word.toCharArray()) { if (node.children[ch] == null) node.children[ch] = new TrieNode(ch); node = node.children[ch]; } node.isEnd = true; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //insert a word into the trie, iteration, Time O(s), Space O(s), s is word length insert(word) { if (this.search(word) == true) { System.out.println(word + " is already in trie."); return; } let node = this.root; for (let ch of word) { if (node.children[ch] == null) node.children[ch] = new TrieNode(ch); node = node.children[ch]; } node.isEnd = true; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 | #inserts a word into the trie, Iteration, Time O(s), Space O(s), s is word length def insert(self, word): if self.search(word) == True: print(word + " is already in trie.") return node = self.root for ch in word: idx = ord(ch) if not node.children[idx]: node.children[idx] = TrieNode(ch) node = node.children[idx] node.isEnd = True |
Doodle
Delete a string
To delete a string from the trie, first check whether the string exists in the trie. If not, the method can return. For each character in the string, examine if the node’s children have a value at the index of the character. If yes, use the character as the index to locate the corresponding node and move to that node. When reaching the last node, set the node’s isEnd to be false. The string is still in the trie, but unsearchable.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length void delete(String word) { if (this.search(word) == false) { System.out.println(word + " does not exist in trie."); return; } TrieNode node = root; for (char ch : word.toCharArray()) { if (node.children[ch] == null) return; node = node.children[ch]; } node.isEnd = false; } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | //Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length delete(word) { if (this.search(word) == false) { console.log(word + " does not exist in trie."); return; } let node = this.root; for (let ch of word) { if (node.children[ch] == null) return; node = node.children[ch]; } node.isEnd = false; } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 | #Remove a word, Iteration, Time O(s), Space O(1) def delete(self, word): if self.search(word) == False: print(word + " does not exist in trie.") return node = self.root for ch in word: index = ord(ch) if not node.children[index]: return node = node.children[index] node.isEnd = False |
Search a string
To search a string in the trie, start from root and loop through each character in the string. If the node’s children don’t have a value at the index of the character, the method returns false. Otherwise, move to the child node by the reference stored in children. When reaching the last node in the branch, return the node’s isEnd value. If the value is false, it indicates the string has been deleted.
Java
1 2 3 4 5 6 7 8 9 10 | //Find word in trie, Iteration, Time O(s) Space O(1), s is word length boolean search(String word) { TrieNode node = root; for (char ch: word.toCharArray()) { if (node.children[ch] == null) return false; node = node.children[ch]; } return node.isEnd; } |
Javascript
1 2 3 4 5 6 7 8 9 10 | //Find a word in trie, Iteration, Time O(s) Space O(1), s is word length search(word) { var node = this.root; for (let ch of word) { if (node.children[ch] == null) return false; node = node.children[ch]; } return node.isEnd; } |
Python
1 2 3 4 5 6 7 8 9 | #Find word in trie, Iteration, Time O(s) Space O(1), s is word length def search(self, key): node = self.root for ch in key: index = ord(ch) if not node.children[index]: return False node = node.children[index] return node.isEnd |
Print all strings in a trie
This is to print all strings in the trie. Similar to the preorder (depth-first search) traversal of a tree, recursion is used to traverse all nodes in a trie. When visiting the node, concatenate characters from previously visited nodes with the character of the current node. When the node’s isEnd is true, the recursion reaches the last character of the string. It indicates the completion of concatenating one string. You can go ahead to add the string to the result list.
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | //Print all words in trie, call recursion function //Time O(n), Space O(n), n is number of nodes in trie void print() { List<String> res = new ArrayList<String>(); helper(root, res, ""); System.out.println(res); } //recursion function, Time O(n), Space O(n), n is number of nodes in trie void helper(TrieNode node, List<String> res, String prefix) { if (node == null ) //base condition return; if (node.isEnd) { String word = prefix + node.data; res.add(word.substring(1)); //skip the first space from root } for (TrieNode child: node.children) helper(child, res, prefix + node.data); } |
Javascript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | //Print all words in trie, call recursion function //Time O(n), Space O(n), n is number of nodes in trie print () { let res = []; this.helper(this.root, res, ""); console.log(res); } //recursion function, Time O(n), Space O(n), n is number of nodes in trie helper(node, res, prefix) { if (node.isEnd) res.push(prefix + node.data); for (let child in node.children) //array this.helper(node.children[child], res, prefix + node.data); } |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #Print all words in trie, call recursion function #Time O(n), Space O(n), n is number of nodes in trie def print (self): res = [] self.helper(self.root, res, "") print(res) #recursion function, Time O(n), Space O(n), n is number of nodes in trie def helper(self, node, res, prefix): if node == None: return if node.isEnd: res.append(prefix + node.data) for child in node.children: self.helper(child, res, prefix + node.data) |
Free download
Download trie implementation using Array in Java, JavaScript and Python
Data structures introduction PDF
What data structures are used to implement a trie?
In a trie, each trie node might have multiple branches. So there is a data structure used to store references to the next nodes in the branches. This data structure can be an array, a linked list, or a hash map.
How to implement a trie in Java?
You implement a trie just like building a tree. You define a TrieNode class first. It has a data structure called children, which is used to store the references to the next nodes in the branches. Then you define a Trie class. It has a root node. You insert a string by adding nodes from the first character to the last.