AlgoDaily - Trie Data Structure

Home > Advanced data structures and algorithms > Advanced data structures and algorithms > Trie Data Structure

To construct a trie data structure, we will need to create two classes: Trie and TrieNode.

The TrieNode class represents a single node in the trie, and it contains an array of TrieNode objects called links to represent the next possible characters in the trie. Each TrieNode also has a boolean property isEnd to mark the end of a word.

Here is an example implementation of the TrieNode class in Java:

TEXT/X-JAVA

1public class TrieNode {
2    private TrieNode[] links;
3    private boolean isEnd;
4
5    public TrieNode() {
6        links = new TrieNode[26];
7    }
8
9    public boolean containsKey(char ch) {
10        return links[ch - 'a'] != null;
11    }
12
13    public TrieNode get(char ch) {
14        return links[ch - 'a'];
15    }
16
17    public void put(char ch, TrieNode node) {
18        links[ch - 'a'] = node;
19    }
20
21    public boolean isEnd() {
22        return isEnd;
23    }
24
25    public void setEnd() {
26        isEnd = true;
27    }
28}

The Trie class represents the trie itself and provides methods to insert a word, search for a word, and check if a word starts with a given prefix.

Here is an example implementation of the Trie class in Java:

TEXT/X-JAVA

1public class Trie {
2    private TrieNode root;
3
4    public Trie() {
5        root = new TrieNode();
6    }
7
8    public void insert(String word) {
9        TrieNode current = root;
10        
11        for (char ch : word.toCharArray()) {
12            if (!current.containsKey(ch)) {
13                current.put(ch, new TrieNode());
14            }
15            
16            current = current.get(ch);
17        }
18        
19        current.setEnd();
20    }
21
22    public boolean search(String word) {
23        TrieNode current = searchPrefix(word);
24        
25        return current != null && current.isEnd();
26    }
27
28    public boolean startsWith(String prefix) {
29        return searchPrefix(prefix) != null;
30    }
31
32    private TrieNode searchPrefix(String prefix) {
33        TrieNode current = root;
34        
35        for (char ch : prefix.toCharArray()) {
36            if (!current.containsKey(ch)) {
37                return null;
38            }
39            
40            current = current.get(ch);
41        }
42        
43        return current;
44    }
45}

xxxxxxxxxx
}
 
public class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode current = root;
        
        for (char ch : word.toCharArray()) {
            if (!current.containsKey(ch)) {
                current.put(ch, new TrieNode());
            }
            
            current = current.get(ch);
        }
        
        current.setEnd();
    }
    
    public boolean search(String word) {
        TrieNode current = searchPrefix(word);
        
        return current != null && current.isEnd();
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;

Programming Categories

Popular Lessons