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.
Why is a singly linked list used in a trie node?
In a trie, 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. Each implementation has its pros and cons. In the array implementation, you have to initialize the array size, which leads to a large amount of unused space. A linked list overcomes this problem by storing references to the following nodes in a chain. However, this requires time to search for the character’s corresponding reference in the list. So this implementation uses time to trade space.
Table of Content
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, 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 linked list of children nodes. isEnd is to mark whether this is the last node of the branch. In the TrieNode class, the getChild() method returns the reference of the node by the input character.
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 19 20 21 22 23 24 25 26 27 28 |
import java.util.*; public class TrieList { 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, //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; } } 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 |
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 in trie implementation
To insert a string, first check whether the string is in the trie so that you don’t insert a duplicate string You start from root, and loop through each character in the string. 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 has the last character of the string, you mark the node’s isEnd to be true.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//Add a word to tire, Iteration, Time O(s*k), 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()) { TrieNode n = node.getChild(ch); if (n == null) { TrieNode newNode = new TrieNode(ch); node.children.add(newNode); node = newNode; } else node = n; } node.isEnd = true; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
//insert a word into the trie, Time O(s*k), 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) { var n = node.getChild(ch); if (n == null) { let newNode = new TrieNode(ch); node.children.push(newNode); node = newNode; } else node = n; } node.isEnd = true; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#Add a word to trie, Iteration, Time O(s*k), 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: n = node.getChild(ch) if n == None: newNode = TrieNode(ch) node.children.append(newNode) node = newNode else: node = n node.isEnd = True |
Doodle
Delete
To delete a string from a trie, first check whether the string exists in the trie. If not, the method can return. You start from root and loop through each character in the string. If the next character is in the node’s children, the node moves to the child node. When the node has the last character of the string, mark 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 15 |
//Remove a word from trie, Iteration, Time O(s*k), 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()) { TrieNode n = node.getChild(ch); if (n == null) return; node = n; } node.isEnd = false; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//Remove a word from trie, Iteration, Time O(s*k), 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) { let n = node.getChild(ch); if (n == null) return; node = n; } node.isEnd = false; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#Remove a word from trie, Iteration, Time O(s*k), 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: n = node.getChild(ch) if n == None: return node = n node.isEnd = False |
Search
To search for a string in a trie, you start from root and loop through each character in the string. 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 has the last character of the string, 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 11 |
//Search a word in trie, Iteration, Time O(s*k), Space O(1), s is word length boolean search(String word) { TrieNode node = root; for (char c : word.toCharArray()) { TrieNode n = node.getChild(c); if (n == null) return false; node = n; } return node.isEnd; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 |
//Search a word in trie, Iteration, Time O(s*k), Space O(1), s is word length search(word) { var node = this.root; for (let ch of word) { let n = node.getChild(ch); if (n == null) return false; node = n; } return node.isEnd; } |
Python
|
1 2 3 4 5 6 7 8 9 |
#Search a word in trie, Iteration, Time O(s*k), Space O(1), s is word length def search(self, word): node = self.root for ch in word: n = node.getChild(ch) if n == None: return False node = n return node.isEnd |
Print
To print all strings in a trie, recursion is used to traverse all nodes in the trie. This is similar to the preorder (depth-first search) traversal 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 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 |
//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 trie implementation using linked list in Java, JavaScript and Python
Data structures introduction PDF