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. Insert a word in a trie, search a word, or delete a word by key all takes O(n) time, at the expense of storage. In this post, we implement trie using linked lists.
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. In array implementation, the next character in the node will be used as the index to find the child nodes. However, most cells in the array are empty which is not space efficient. A linked list overcomes this problem by creating nodes only for the next characters in branches. But this require time to find the right child by search each node in the list. So this implementation uses time to trade space.
Table of Content
Define classes
Like building a tree, you need to define a TrieNode class before a Trie class. The trie node class has tree variables: data, children, and isEnd. data stores a character, children is a data structure that points to the children nodes; isEnd is to mark whether this is the last node of the branch.
In Trie class, there is one 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 20 21 22 23 24 25 26 27 |
public class TrieList { static class TrieNode { char data; LinkedList<TrieNode> children = new LinkedList<>(); boolean isEnd = false; //Constructor, Time O(1), Space O(1) TrieNode(char c) { this.data = c; } //find the node by char, the same functionality as children[ch] in array implementation //Time O(k), Space O(1), k is number of children of this node TrieNode getChild(char c) { if (children != null) for (TrieNode ch : children) if (ch.data == c) return ch; return null; } } 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 18 19 20 21 22 23 24 25 26 27 |
class TrieNode { //Constructor, Time O(1), Space O(1) constructor(c) { this.data = c; this.children = []; //List this.isEnd = false; } //find the node by char, the same functionality as children[ch] in array implementation //Time O(k), Space O(1), k is number of children of this node getChild(c) { if (this.children != null) for (let child of this.children) if (child.data == c) return child; return null; } } 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 14 15 16 17 18 19 20 21 |
class TrieNode: #Constructor, Time O(1), Space O(1) def __init__(self, c): self.data = c self.children = [] # list self.isEnd = False #find the node by char, the same functionality as children[ch] in array implementation #Time O(k), Space O(1), k is number of children of this node def getChild(self, c): if self.children != None: for child in self.children: if child.data == c: return child return None 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. Then you loop through each character in the word. A pointer node starts from root. If the character is not in the node‘s children, a child node is created. Then the pointer moves to the child node. When the pointer is at 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 |
//Add a word to tire, 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.getChild(ch) == null) node.children.add(new TrieNode(ch)); node = node.getChild(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, 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; } var node = this.root; for (let ch of word) { if (node.getChild(ch) == null) node.children.push(new TrieNode(ch)); node = node.getChild(ch); } node.isEnd = true; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Add a word to 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: if node.getChild(ch) == None: node.children.append(TrieNode(ch)) node = node.getChild(ch) 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. Loop through each character in the word. A pointer node starts from root. If the next character is not in the node‘s children, the method returns directly. Otherwise, the pointer moves to the child node. When the pointer is at the last character of the word, mark the node‘s isEnd to be false.
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.getChild(ch) == null) return; node = node.getChild(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.getChild(ch) == null) return; node = node.getChild(ch); } node.isEnd=false; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Remove a word from trie, Iteration, Time O(s), Space O(1), s is word length def delete(self, word) : if self.search(word) == False: print(word + " does not exist in trie.") return node = self.root for ch in word: if (node.getChild(ch) == None) : return node = node.getChild(ch) node.isEnd = False |
Search a word
To search a word in a trie, loop through each character in the word. A pointer node starts from root. If the character is not in the node‘s children, the method returns false. Otherwise, the pointer moves to the child node. When the pointer is at 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 |
//Search a word in trie, Iteration, Time O(s), Space O(1), s is word length boolean search(String word) { TrieNode node = root; for (char c : word.toCharArray()) { if (node.getChild(c) == null) return false; node = node.getChild(c); } return node.isEnd; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Search 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.getChild(ch) == null) return false; node = node.getChild(ch); } return node.isEnd; } |
Python
|
1 2 3 4 5 6 7 8 |
#Search a word in trie, Iteration, Time O(s), Space O(1), s is word length def search(self, word) : node = self.root for ch in word : if node.getChild(ch) == None: return False node = node.getChild(ch) return node.isEnd |
Print all words in a trie
To print all words in a trie, recursion is used to traverse all nodes in the trie. This is similar to preorder (DFS, depth first search) of a tree. 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, and 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 |
//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.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 of node.children) //list this.helper(child, res, prefix + node.data); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#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.isEnd: res.append(prefix + node.data); for child in node.children: self.helper(child, res, prefix + node.data) |
Free download
Download TrieList.java
Download TrieList.js
Download TrieList.py
Coding tutorial in YouTube
Implement trie using arrays
