Trie Data Structure - Insert Operation
Tags: java, algorithms, tutorial, interview
Published: 2021-05-09 06:16:18

# 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.

```Java
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.

![1](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h4wms8qgk9uincw5k6o3.png)

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 :

![Untitled drawing](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jms2u2q2fbxsopgsm5d8.jpg)


# Time Complexity : 
O(number of words * maxLengthOfWord)

# Space Complexity : 
O(number of words * maxLengthOfWord)

# Code : 

```Java
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);
        }
}
```
# Resources for trie : 

{% github Rohithv07/LeetCodeTopInterviewQuestions %}

{% github Rohithv07/LeetCode %}

{% youtube 6PX6wqDQE20 %}

This video is a great one to know about trie.