Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in Java

Insertion in a Trie

Explore the method of inserting words into a Trie data structure, including handling cases with no common prefix, shared prefixes, and existing words. Understand the process of setting end-of-word markers and the time complexity of the insertion operation, to build efficient string storage and retrieval systems in Java.

We'll cover the following...

Inserting a word in Trie

Insertion is simple for individual characters in the trie. If the character is already present, we follow the path; if that character is not present, then we insert the corresponding nodes. While inserting the last node, we must also set the value of isEndWord() to true.

Case 1: What if the word has no common subsequence? i.e. No Common Prefix

For example, if we want to insert a new word into the trie below, e.g. “any”, then we need to insert all of the characters for the word “any”; currently, “the” is the only word in the trie, and there are no common character subsequences between “any” and “the”.

Case 2: If the word has a common subsequence? i.e. Common Prefix Found

For example, if we want to insert the word “there” into the trie below-- which already consists of the word “ their”–then the path to “ the” already exists. After that, we need to insert two nodes for “e” and “r” as shown below.

Case 3: If the word is already present? i.e. Common Prefix Found

For example, if we want to insert the word “the” into the trie below-- which consists of a word “ their”–then the path for “ the” already exists. Therefore, we simply need to set the value of isEndWord() to true at “e” in order to represent the end of the word for “the” as shown below.

Implementation

The following is the code snippet, so try to understand the code. If you don’t understand any point, you can read the explanation below.

If this Code had a Face

Java
class Trie{
    private TrieNode root; //Root Node
    //Constructor
    Trie(){
        root = new TrieNode();
    }
    //Function to get the index of a character 'x'
    public int getIndex(char x)
    {
        return x - 'a';  // the index is based on the position of character in alphabets
    }
    //Function to insert a key in the Trie
    public void insert(String key)
    {
        if(key == null) //Null keys are not allowed
        {
            System.out.println("Null Key can not be Inserted!");
            return;
        }
        key = key.toLowerCase(); //Keys are stored in lowercase
        TrieNode currentNode = this.root;
        int index = 0; //to store character index
        //Iterate the Trie with given character index,
        //If it is null, then simply create a TrieNode and go down a level
        for (int level = 0; level < key.length(); level++)
        {
            index = getIndex(key.charAt(level));
            if(currentNode.children[index] == null)
            {
                currentNode.children[index] = new TrieNode();
            }
            currentNode = currentNode.children[index];
        }
        //Mark the end character as leaf node
        currentNode.markAsLeaf();
    }
}

Explanation

The Insert() function (line # 14) takes an argument of a string key, indicating a word which will be stored for that particular word/key.

Null-keys are not allowed, and keys are stored in lowercase.

We simply iterate the key character by character, and we generate an index for each character using getIndex() (line # 9). Afterward, we check the child of currentNode at that particular index, and if it’s null then we create a new TrieNode at that index indicating the specific character of the given key.

In the end, we mark the currentNode as leaf; i.e we’re setting the last character as the end of the word we just stored as “key”.

Time Complexity

If the length of the word is hh, the worst-case time complexity is O(h)O(h). In the worst case, at every level, i.e., for every character in the word, a TrieNode is created and inserted into the Trie. The running time of the TrieNode constructor is O(d)O(d). Since the alphabet size is fixed, this is O(1)O(1). Thus, the running time of inserting in the trie is O(h)O(h).

In this lesson, we have learned how to insert a word in Trie.