A trie is a tree-like data structure in which every node stores a character. A trie can store multiple words. 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. In this post, we implement trie using Arrays in Java, Python and JavaScript.
Note: In a trie, a trie node might have multiple branches. So there is a data structure used to point to next nodes in branches. The data structure can be an array, a linked list or a hash map. Using an array is the most intuitive implementation.
Table of Content
Define classes
Like building a tree, you need to define a TrieNode class before a Trie class. A TrieNode class has three variables: data, children, and isEnd. data stores a character (e.g a letter). children is a data structure that points to children (branches) nodes. The data structure is an array. If you use only alphabet a-z, the length of the array is 26. Here we define the array length to be 128 so that it can hold most ASCII characters, such as ‘ ‘ or ‘#’. isEnd is to mark whether this is the last node in this branch (i.e. the last letter in a word).
In Trie class, there is one class variable root. The operation of insertion, search or deletion always starts from root.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class TrieArray { //don't use 26 if there is space or any other special characters static final int NUM_OF_CHARS = 128 ; static 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; } } static class Trie { TrieNode root = new TrieNode(' '); } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
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 word
To insert a word, first check whether the word is already stored in the trie so that you don’t insert a duplicate word. Start from root, loop through each character in the word. Use the character as the index to find the cell in the current node’s children. Create a child node to store the character and store the node in this cell. Then move to the child node. When it is the last character of the word, you 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 |
Delete a word
To delete a word from a trie, first check whether the word exists in the trie. If not, the method can return. Otherwise, continue. Start from root, loop through each character in the word. If the character is not in the node‘s children, the method returns directly. Otherwise, move to the child node. When it is the last character of the word, mark the node‘s isEnd to be false. The word is not actually deleted from the trie. It just becomes inaccessible.
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 word
To search a word in a trie, start from root and loop through each character in the word. If the character is not in the node‘s children, the method returns false. Otherwise, move to the child node. When it is the last character of the word, return the node‘s isEnd value, which can be true or false.
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 words in a trie
This is to print all words in a trie. Similar to preorder (DFS, depth first search) 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 word. Add the word to the result list.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
//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 TrieArray.java
Download TrieArray.js
Download TrieArray.py
Coding tutorial in YouTube
Implement trie using hashmaps
