Introduction to Trie Data Structure - The Coding Shala

Last Updated: 26-Jan-2021

Home >> Data Structures >> Introduction to Trie Data Structure

 In this post, we will learn what is Trie Data Structure and how to implement Trie in Java.

Introduction to Trie Data Structure

Trie is a special form of an N-ary tree, also called prefix tree. Tries are an extremely special and useful data-structure are based on the prefix of a string. They are used to represent the Retrieval of data and thus the name Trie.

A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of at max 26 children and edges connect each parent to its children. These 26 pointers are nothing but pointers for each of the 26 letters of the English alphabet. 

Note: Root node is null in Trie.

Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All prefixes of length 1 are stored until level 1, all prefixes of length 2 are sorted until level 2, and so on.

Here is an Example of Trie Data Structure:

null             Strings stored

      /    |   \               - am

   a      b    s             - bad

   |      / \    |             - be

  m   a   e  o        - so

         |

d

In the above example, if we start from the root node and choose the second path 'b' then choose the first child 'a' and choose child 'd' then we finally make the string "bad". 

One important property of Trie is that all the descendants of a node have a common prefix of the string associated with that node. That's why Trie is also called prefix tree.

Now the question comes to mind how do we represent Trie?

We can use the array to store children nodes. We can declare an array whose size is 26 in each node to store its children nodes. The following code explains it: 

class TrieNode{
	public static final N = 26;
	public TrieNode[] children = new TrieNode[N];
}

This method is fast to visit a child node but every time we don't need every child so this might be some waste of space.

The second method is to use a hashMap to store children nodes. We can declare a hashMap in each node. The key of the hashMap are children and the value is the corresponding child node.

The following code explains it: 

class TrieNode{
	public Map<Character, TrieNode> children = new HashMap<>();
}

In Trie, we perform some important operations like insertion, search, delete, etc.

Insertion in Trie

While we insert a target value into a Trie, first we will decide which path to go depending on the target value we insert. We traverse all the Character nodes sequentially and reach the end. The end node will be the node that represents the whole string.

Search in Trie

Either we can search Prefix or the whole word in a Trie. We know all the descendants of a node have a common prefix of the string associated with that node. We can go down the Trie depending on the given prefix. If we can not find the child node we want, our search fails otherwise it succeeds. Similarly, we can search the whole word. In Words, we need to check if the target word is the only prefix of the word in Trie means the last node of the word does not have any children.

Basic Implementation of Trie Data Structure

The following program explains the basic implementation of Trie Data Structure. 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

Java Program to Implement Trie using Array

Java Program: 

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

class Trie {
    TrieNode root;
    
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        for(char ch : word.toCharArray()){
            if(curr.children[ch-'a'] == null){
                curr.children[ch-'a'] = new TrieNode();
            }
            curr = curr.children[ch-'a'];
        }
        curr.isEndOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode curr = root;
        for(char ch : word.toCharArray()){
            if(curr.children[ch-'a']==null){
                return false;
            }
            curr = curr.children[ch-'a'];
        }
        if(curr.isEndOfWord) return true;
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for(char ch : prefix.toCharArray()){
            if(curr.children[ch-'a']==null){
                return false;
            }
            curr = curr.children[ch-'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Java Program to Implement Trie using HashMap

Java Program: 

class TrieNode{
    Map<Character, TrieNode> child;
    boolean isEndOfWord;
    TrieNode(){
        this.child = new HashMap<Character, TrieNode>();
        this.isEndOfWord = false;
    }
}

class Trie {
    TrieNode root;
    
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode curr = root;
        for(char ch : word.toCharArray()){
            if(!curr.child.containsKey(ch)){
                curr.child.put(ch, new TrieNode());
            }
            curr = curr.child.get(ch);
        }
        curr.isEndOfWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode curr = root;
        for(char ch : word.toCharArray()){
            if(!curr.child.containsKey(ch)){
                return false;
            }
            curr = curr.child.get(ch);
        }
        if(curr.isEndOfWord) return true;
        return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode curr = root;
        for(char ch : prefix.toCharArray()){
            if(!curr.child.containsKey(ch)){
                return false;
            }
            curr = curr.child.get(ch);
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

Other Posts You May Like

• Introduction to Binary Tree
• Introduction to Binary Search Tree
• Introduction to N-ary Tree
• Search in a Binary Search Tree
• Delete Node in a Binary Search Tree

Please leave a comment below if you like this post or found some errors, it will help me to improve my content.