Skip to main content

Trie

Introduction to Trie​

Coverage-Trie BorderRadius8

A trie, or a prefix tree, is a type of search tree that is usually used to store strings. Some of the properties of Trie are:
➡️ Each path from the root to leaves forms a word.
➡️ Each node except for the root node contains a value.
➡️ All the descendants of a node share a common prefix associated to that node. For example, are and art share ar as the prefix.

➡️ Trie Operations: inserting a new string, and searching for a given string.

Implementation of Trie​

General Function Calls around Trie​

Implement a trie with insert, search, and startsWith methods.

Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.

Implementation of Trie - Java​

Define TrieNode​

Class TrieNode:

➡️ A boolean variable isWord to indicate whether we can form a word or it's only a prefix.
➡️ An array of TrieNode named children to store its children node.
➡️ A constructor which initializes isWord to false, and children array of 26 letters(lowercase) will be used.

class TrieNode {    TrieNode[] children;    boolean isEndOfWord;    public TrieNode() {        children = new TrieNode[26];        isEndOfWord = false;    }}

Insertion into Trie​

Given a new string word, we would iterate through it. Starting from the dummy node root and the first character c, we would check whether c is in root.children:

➡️ if it is, we can move to that node and increment to next character as well;
➡️ if not, we need to initiate a new node so that we can attach c to the trie.

public void insert(String word) {
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (node.children[index] == null) {
            node.children[index] = new TrieNode();
        }
        node = node.children[index];
    }
    node.isEndOfWord = true;
}
//Time Complexity: O(L) where L is the length of the word.

Searching in Trie​

Similarly to insert, we also start the iteration with the first character and the dummy node. If we do not find the character in its children, we can return false. Remember to check isWord after reaching the end of word.
public boolean search(String word) {
    TrieNode current_node = root;
    for (int i = 0; i < word.length(); i++) {
        int index = word.charAt(i) - 'a';
        if (current_node.children[index] == null) return false;
        current_node = current_node.children[index];
    }
    return current_node.isWord;
}

//Time Complexity: O(L) where L is the length of the word.

StartsWith in Trie​

The only different to search is that, we do not need to check isWord at the end.

public boolean startsWith(String prefix) {
    TrieNode current_node = root;
    for (int i = 0; i < prefix.length(); i++) {
        int index = prefix.charAt(i) - 'a';
        if (current_node.children[index] == null) return false;
        current_node = current_node.children[index];
    }
    return true;
}
//Time Complexity: O(L) where L is the length of the prefix.

Visualization of Trie​

Trie Insertion

References​