Trie DataStructure Implementation in Java

In this article, we will discuss one of the string algorithms - Tries which reduces the time complexity of search operation. We will see how Trie DS can be implemented in Java and perform the search operations.

A trie is a tree where each node may contain the number of pointers equal to the number of characters of the alphabet. With Tries, the insertion and search operation of any String can be performed in O(L) where L is the length of the given string.

Hence, Trie data structure is much faster than the hash table and binary search tree representation.

Trie Node Implementation

A trie node contains a Map(char, node) and isWord(boolean). The value of isWord to true corresponds to a complete word.

public class TrieNode {

    Map<Character, TrieNode> node;
    boolean isWord;

    public TrieNode(){
        this.node = new HashMap<>();
    }

Below is a sample structure of a Trie data structure.

Different Trie Operations

Trie datastructure has mainly two operations - insert and search.

Insert Operation

For insertion in a trie, we need to start with the root node and follow the path with each character present in the given word. Once, we reach the NULL node, we simply create a new Trie node with isWord flag as false and put the character in the map of previous Trie node and store the reference of the newly created Trie node in the previous node and move the pointer to the newly created Trie node.

Once, we reach to the end of the word then we update the boolean flag isWord as true of current node.

public class Trie {

    private TrieNode root;

    public Trie(){
        this.root = new TrieNode();
    }

    public void insert(String word){
        TrieNode current = root;
        int length = word.length();
        for (int i = 0; i < length; i++){
            char letter = word.charAt(i);
            TrieNode node = current.getNode().get(letter);
            if (node == null){
                node = new TrieNode();
                current.getNode().put(letter, node);
            }
            current = node;
        }
        current.setWord(true);
    }

}

Search Operation

Search operation in a Trie DS is very similar to insert operation. We simply start from the root node and follow the pointers. The boolean flag isWord helps to identify the end of the word.

public boolean isCompleteWord(String word){
        TrieNode current = root;
        int length = word.length();
        for (int i = 0; i < length; i++){
            char letter = word.charAt(i);
            TrieNode node = current.getNode().get(letter);
            if (node == null){
                return false;
            }
            current = node;
        }
        return current.isWord;
    }

Similarly, prefix search is also follows the same process.

public boolean isValidPrefix(String prefix){
        TrieNode current = root;
        int length = prefix.length();
        for (int i = 0; i < length; i++){
            char letter = prefix.charAt(i);
            TrieNode node = current.getNode().get(letter);
            if (node == null){
                return false;
            }
            current = node;
        }
        return current != null;
    }

Trie Runner Class

public static void main(String[] args){
        Trie trie = new Trie();
        trie.insert("dhiraj");
        trie.insert("niraj");
        System.out.println(trie.isCompleteWord("dhiraj"));
        System.out.println(trie.isValidPrefix("dha"));
        System.out.println(trie.isValidPrefix("ni"));
}

Disadvantages of Tries

One main Disadvantage of Trie DS is that it requires a lot of memory for storing the strings. To overcome this issue, Ternary Search tree is used which combines the memory efficiency of BSTs and time efficiency of tries.

Conclusion

In this article, we discussed Trie datastructure and implemented in Java and perform the search operations.