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;

Are you sure you're getting this? Is this statement true or false?

In a trie data structure, each node contains links to the next possible characters in the trie.

Press true if you believe the statement is correct, or false otherwise.

To insert a new word into a trie, we can use the following steps:

Start from the root node and initialize a pointer current to track the current node.
Iterate through each character in the word.
Check if the current node contains a link for the character. If not, create a new node and add the character as a link.
Update the current pointer to the newly created node.
Repeat steps 3-4 for all characters in the word.
After iterating through all characters, mark the current node as the end of a word.

Here is an example implementation of the insert method in the Trie class:

TEXT/X-JAVA

1public void insert(String word) {
2    TrieNode current = root;
3
4    for (int i = 0; i < word.length(); i++) {
5        char ch = word.charAt(i);
6
7        if (!current.containsKey(ch)) {
8            current.put(ch, new TrieNode());
9        }
10
11        current = current.get(ch);
12    }
13
14    current.setEnd();
15}

xxxxxxxxxx
 
// Implementing Trie Insertion
​
public class Trie {
    private TrieNode root;
​
    public Trie() {
        root = new TrieNode();
    }
​
    public void insert(String word) {
        TrieNode current = root;
​
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
​
            if (!current.containsKey(ch)) {
                current.put(ch, new TrieNode());
            }
​
            current = current.get(ch);
        }
​
        current.setEnd();
    }
}

Let's test your knowledge. Click the correct answer from the options.

Which of the following steps are involved in inserting a new word into a trie?

A) Traverse the trie until the end of the word B) Start from the root node and initialize a pointer C) Create a new node for each character D) Mark the last node as the end of the word

Select the correct options:

Click the option that best answers the question.

In a trie, deletion refers to removing a word from the trie.

The deletion operation can be done by following these steps:

Start from the root node and initialize a pointer current to track the current node.
Iterate through each character in the word.
Check if the current node contains a link for the character. If not, return false as the word is not present in the trie.
Update the current pointer to the next node.
Repeat steps 3-4 for all characters in the word.
After iterating through all characters, check if the current node is the end of a word. If not, return false as the word is not present in the trie.
Mark the current node as not the end of a word.
Check if the current node has any children. If not, remove the link to the current node from its parent.
Repeat steps 7-8 for all characters in the word, from the last character to the first.

Here is an example implementation of the delete method in the Trie class:

TEXT/X-JAVA

1public void delete(String word) {
2    delete(root, word, 0);
3}
4
5private boolean delete(TrieNode current, String word, int index) {
6    if (index == word.length()) {
7        if (!current.isEndOfWord()) {
8            return false;
9        }
10        current.setEndOfWord(false);
11        return current.getChildren().isEmpty();
12    }
13
14    char ch = word.charAt(index);
15    TrieNode node = current.getChildren().get(ch);
16    if (node == null) {
17        return false;
18    }
19
20    boolean shouldDeleteCurrentNode = delete(node, word, index + 1);
21    if (shouldDeleteCurrentNode) {
22        current.getChildren().remove(ch);
23        return current.getChildren().isEmpty();
24    }
25
26    return false;
27}

xxxxxxxxxx
}
 
class TrieNode {
    private Map<Character, TrieNode> children;
    private boolean isEndOfWord;
​
    public TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
​
    public Map<Character, TrieNode> getChildren() {
        return children;
    }
​
    public boolean isEndOfWord() {
        return isEndOfWord;
    }
​
    public void setEndOfWord(boolean endOfWord) {
        isEndOfWord = endOfWord;
    }
}
​
class Trie {
    private TrieNode root;
​
    public Trie() {
        root = new TrieNode();
    }
​

Let's test your knowledge. Is this statement true or false?

In a trie, deletion refers to removing a word from the trie.

Press true if you believe the statement is correct, or false otherwise.

To search for a word in a trie, follow these steps:

Start from the root node and initialize a pointer current to track the current node.
Iterate through each character in the word.
Check if the current node contains a link for the character. If not, the word is not present in the trie.
Update the current pointer to the next node.
Repeat steps 3-4 for all characters in the word.
After iterating through all characters, check if the current node marks the end of a word. If yes, the word is present in the trie. Otherwise, the word is not present.

Here is an example implementation of the search method in the Trie class:

xxxxxxxxxx
 
class Trie {
​
    // ... other methods
​
    public boolean search(String word) {
        TrieNode current = root;
​
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            TrieNode node = current.getChildren().get(ch);
​
            // If the current node doesn't contain a link for the character,
            // the word is not present in the trie
            if (node == null) {
                return false;
            }
​
            current = node;
        }
​
        // After iterating through all characters,
        // the word is present if the current node marks the end of a word
        return current.isEndOfWord();
    }
​
    // ... other methods
​
}

Build your intuition. Click the correct answer from the options.

What is the time complexity of searching for a word in a trie with n nodes?

Click the option that best answers the question.

O(log n)
O(n)
O(m)
O(1)

A practical use case of tries is autocomplete functionality. Tries provide an efficient way to implement autocomplete or suggestion features in text editors or search engines.

In an autocomplete system, given a prefix entered by the user, the system needs to suggest a list of words that match that prefix. For example, if the user types "app", the system should suggest words like "apple" and "application".

Tries are well-suited for this task because they can efficiently find all words that match a given prefix. Starting from the root node, we can navigate through the trie following the characters in the prefix. If we reach a node where the characters don't match, we can immediately stop the traversal and return an empty list of suggestions. If we reach the end of the prefix, we can use a depth-first search to find all words below that node, which provides us with the autocomplete suggestions.

Here's an example implementation of an autocomplete class using a trie in Java:

TEXT/X-JAVA

1import java.util.ArrayList;
2import java.util.List;
3
4public class Autocomplete {
5
6    private TrieNode root;
7
8    public Autocomplete() {
9        root = new TrieNode();
10    }
11
12    // Insert a word into the trie
13    public void insert(String word) {
14        TrieNode current = root;
15
16        for (char c : word.toCharArray()) {
17            int index = c - 'a';
18            if (current.children[index] == null) {
19                current.children[index] = new TrieNode();
20            }
21            current = current.children[index];
22        }
23
24        current.isWord = true;
25    }
26
27    // Get autocomplete suggestions for a given prefix
28    public List<String> autocomplete(String prefix) {
29        TrieNode current = root;
30        List<String> suggestions = new ArrayList<>();
31
32        for (char c : prefix.toCharArray()) {
33            int index = c - 'a';
34            if (current.children[index] == null) {
35                return suggestions;
36            }
37            current = current.children[index];
38        }
39
40        autocompleteHelper(prefix, current, suggestions);
41
42        return suggestions;
43    }
44
45    private void autocompleteHelper(String prefix, TrieNode node, List<String> suggestions) {
46        if (node.isWord) {
47            suggestions.add(prefix);
48        }
49
50        for (char c = 'a'; c <= 'z'; c++) {
51            int index = c - 'a';
52            if (node.children[index] != null) {
53                autocompleteHelper(prefix + c, node.children[index], suggestions);
54            }
55        }
56    }
57
58    private class TrieNode {
59        TrieNode[] children;
60        boolean isWord;
61
62        public TrieNode() {
63            this.children = new TrieNode[26];
64            this.isWord = false;
65        }
66    }
67
68    public static void main(String[] args) {
69        Autocomplete autocomplete = new Autocomplete();
70        autocomplete.insert("apple");
71        autocomplete.insert("application");
72        autocomplete.insert("banana");
73
74        List<String> suggestions = autocomplete.autocomplete("app");
75        System.out.println(suggestions); // Output: [apple, application]
76    }
77}

xxxxxxxxxx
}
 
```java
import java.util.ArrayList;
import java.util.List;
​
public class Autocomplete {
​
    private TrieNode root;
​
    public Autocomplete() {
        root = new TrieNode();
    }
​
    // Insert a word into the trie
    public void insert(String word) {
        TrieNode current = root;
​
        for (char c : word.toCharArray()) {
            int index = c - 'a';
            if (current.children[index] == null) {
                current.children[index] = new TrieNode();
            }
            current = current.children[index];
        }
​
        current.isWord = true;
    }
​
    // Get autocomplete suggestions for a given prefix
    public List<String> autocomplete(String prefix) {

Are you sure you're getting this? Is this statement true or false?

Tries are efficient data structures for implementing autocomplete functionality in text editors or search engines.

Press true if you believe the statement is correct, or false otherwise.

Generating complete for this lesson!

Are you sure you're getting this? Is this statement true or false?

Let's test your knowledge. Click the correct answer from the options.

Click the option that best answers the question.

Let's test your knowledge. Is this statement true or false?

Build your intuition. Click the correct answer from the options.

Click the option that best answers the question.

Are you sure you're getting this? Is this statement true or false?

Programming Categories

Popular Lessons