# 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);
}
}
```

# Resources for trie :

## Rohithv07 / LeetCodeTopInterviewQuestions

### Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions

# LeetCodeTopInterviewQuestions

Leetcode Top Interview questions discussed in Leetcode. https://leetcode.com/explore/interview/card/top-interview-questions-easy/

Also Question answered from CodeSignal.com : https://app.codesignal.com/

This video is a great one to know about trie.

## Discussion (0)