Trie implementation is to implement a data structure trie. A trie is a tree-like data structure in which every node stores a character. After building the trie, strings or substrings can be retrieved by traversing down a path of the trie. Tries are used for find-substrings, auto-complete and many other string operations. Here trie is implemented in Java, Python and JavaScript.
Table of Content
- Map of trie implementations
- Define classes
- Insert a word
- Delete a word
- Search a word
- Print all words in trie
- Free download
Map of trie implementations
Array is the most intuitive implementation. In this post, This post is trie implemented using array.
Part 1 – Trie implementation using array.
Part 2 – Trie implementation using linked list
Part 3 – Trie implementation using hash map
Define classes in trie implementation
The trie node class has three variables: data stores a character, children is a data structure that points to the children (branches) nodes. The data structure is array. If you use only alphabet a-z, the length of array is 26. Here we define the array length to be 128 so that it can hold most ASCII characters; isEnd is to mark whether this is the last node to compose a word. The trie class, there is one class level variable – root. The operation of insert, search or delete always starts from the 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 in trie implementation
To insert a word, first check whether the word is in the trie so that we don’t insert duplicate word. Then we loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, a child node is created. Then the node moves to the child node. When the node is at the last character of the word, we 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 word
To delete a word from the trie, first check whether the word exists in the trie. If not, the method can return. The same as insert, loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, the method returns directly. Otherwise, the node moves to the child node. When the node is at the last character of the word, mark the node‘s isEnd to be false. The word is not actually deleted from the trie. It becomes invisible.
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 the trie, loop through each character in the word. A pointer node starts from the root node. If the character is not in the node‘s children, the method returns false. Otherwise, the node moves to the child node. When the node is at the last character of the word, return the node‘s isEnd value, which can be true or false(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 words in trie
This is to print all words in the trie. Similar to pre-order (DFS, depth first search) of the tree, recursion is used to traverse all nodes in trie. When visiting the node, the method concatenates 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 trie implementation using Array in Java, JavaScript and Python
Download aggregate Data Structures implementations in Java
Download aggregate Data Structures implementations in JavaScript
Download aggregate Data Structures implementations in Python
What are the children in the trie?
A trie normally holds many words. Some characters might have multiple characters following it . For example, “ant”, “add”, “amy” share the same parent node ‘a’. The node ‘a’ has children of ‘n’, ‘d’ and ‘m’. So a trie is a n-ary tree. In the trie node, there is an attribute children, which holds the references to the nodes following it. The children can be stored in a data structure such as array, linked list or hashmap.
How many children a trie node can have?
If you use only alphabet a-z, the size is 26. If you use A-Z and other special characters such as space, the size is 128 or more.
What is time complexity of trie?
Insert a word in trie, search a word and delete a word by key all takes O(s) time, s is the length of the word.