Trie Data Structure - Insert Operation

#java #algorithms #tutorial #interview

Introduction

Trie is a special data structure in which we store the letters of the string. It is very much helpful in finding the longest prefix, longest prefix length, searching of a particular string, finding longest word in dictionary and also for the auto complete system.

Structure

We can structure our trie based on our need. Typically we can have a char ch denoting the character, wordEnd which denotes while inserting the word, whether we reached the end or not, TrieNode[] array = new TrieNode[26] which acts as a pointer which points to the index of the letter we inserted.

class TrieNode {
    char ch;
    TrieNode [] array = new TrieNode[26];
    int wordEnd = 0;
}

So each trie node have a character, a word end and an array for pointing to the letters inserted.

We can do insert operation, search operation and many more using trie.

Insert Operation

In insert operation, we start by creating a root node, which have a wordEnd value of 0, no specific character in it and the TrieNode array.

So, suppose we are inserting a string say s = "abc".
We follow the below steps :

Starting from the root, we check for the index of a which can be found using 'a' - 'a' = 0. At first we check whether array[0] is null or not. Here array[0] is null, so from 0th index in root, we create a new trienode with a new character having a in it, wordEnd = 0 since the string we have to insert is not finished and the array of pointers. Now we move forward to node a.

Next we have to insert b and this time we start from the next node, ie the node of a. Same as above, we find the correct index for b using 'b' - 'a' = 1. Here we check whether array[1] is null or not, if it is null, then a new node for b is created as above with the respective field, otherwise it denotes that we already inserted b and we continue with the next node. In our example abc, a new node for b will be created. Now we move forward to node b.
Note : The wordEnd will be still 0, as we are not finished with our string.

Next we insert c by finding the index 'c' - 'a' = 2. We check whether array[2] is null or not, here it will be null so a new node will be generated for c node.
Here we are finished with the string, so the wordEnd value will be updated to wordEnd = wordEnd + 1.

Let's continue inserting another string s = "abd"

Here again we start from the root, and find the index for the first character, ie a here, which is 'a' - 'a' = 0. So here array[0] is not null, as we already inserted it before, so we continue into the node a without creating a new node.

Next we have to insert b. Finding the index for b which is 'b' - 'a' = 1. Here also while we check array[1] null or not from node a, we can see it is already inserted, so without creating a new node, we move forward to node b.

Next character is d and we find the index for d which is 'd' - 'a' = 3. If we check array[3] == null, we can see it is null, and therefore a new node is created for d.
Since d is the last character of the string, we increment the wordEnd to wordEnd + 1 to indicate we are finished with the string abd.

Let's insert one more string s = "bcd".

Same as above procedure, let's do it once more.

Start from the root, find the index of the first character b which 'b' - 'a' = 1 and its value in array[1] is null, so a new node for b is created and we move forward to node b.

Next character is c and its index = 'c' - 'a' = 2. From node b, if we look for the value of array[2], we get it is null and we create a new node for c and continue with that node.

Next character is d and its index = 'd' - 'a' = 3. From node c, if we look for the value of array[3], we get it is null and a new node is created. Since d is the last character of the string, we increment the wordEnd by wordEnd + 1.

The final structure of the trie after these insertion will be :

Time Complexity :

O(number of words * maxLengthOfWord)

Space Complexity :

O(number of words * maxLengthOfWord)

Code :

class TrieNode {
    char ch;
    TrieNode [] array = new TrieNode[26];
    int wordEnd = 0;
}

public class Trie {
    TrieNode root = null;
    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.array[index] == null) {
                node.array[index] = new TrieNode();
                node.array[index].ch = ch;
                node.array[index].wordEnd = 0;  
            }
            node = node.array[index];
        }
        node.wordEnd += 1;
    }
        public static void main(String [] args) {
            Trie trie = new Trie();
            String a = "abc";
            String b = "abd";
            String c = "bcd";
            trie.insert(a);
            trie.insert(b);
            trie.insert(c);
        }
}