**Introduction**

As we are already familiar with tree data structure, today’s discussion is also on a similar topic as trees. To squeeze the gap of time complexity more, the __trie__ came into existence. More precisely, it was created to compromise time and space complexities in O(N) terms. It is generally pronounced as **‘try’**‘ to differentiate its existence from a tree.

A **trie** is a tree-like data structure wherein the nodes of the tree store the entire alphabets, and strings/ words are **re****trie****ved** by traversing down a branch path of the tree. But let us first see how exactly this trie data structure looks like; let’s dig it out.

**Approach**

In a tree data __Data Structure__, every node has either 0, 1, or 2 children. But in a trie, the number of child nodes possibly depends upon the total number of values. A trie is generally used to store a bunch of words or strings as in a dictionary. In the English alphabet, there are 26 alphabets, so the total number of child nodes is 26. Each trie has an empty root node, which contains references to other nodes, each signifying separate alphabetic values.

A simple trie structure looks like this:

```
struct TrieNode
{
char data;
Int word_end;
TrieNode *child[26]
};
```

So, a trie can be small or big depending on whatever strings it contains. Till now, we have just talked about the root node, but that too is empty, so where do the letters of remaining words take shelter if the root node doesn’t provide them all? Let’s figure it out.

This is a trie structure, containing words: **‘coder,’** ‘**codes**,’** ‘codeless,’ ‘coding’** and **‘doing.’** **‘r,’ ’s,’ ’s’ and ‘g’** are the end nodes(highlighted by yellow color). **‘c’** and **‘d’** are the root nodes. Seen from close, the root nodes look like:

A root node contains a value which is NULL, a reference array to child nodes of size 26. Generally, the value of the root node is an empty string. Typically, this structure is followed for all other nodes, although all are not shown here.

For inserting, let’s take the word **‘code**’; the steps followed are:

The key ‘code’ is already inserted into the trie. What if we wanted to add the word **‘coding’** to this list?

We’d check that this word didn’t already exist. We’d follow the links from one node to another until we reach a NULL node. Then we’d insert the value into the trie.

Word_count shows that many words ending with a particular letter here in this trie. Now, let’s take a look at what searching through our newly-built trie looks like: