 # Trie Data Structure: Explanation and Examples

## What is Trie?

Trie is a sort of k-ary search tree that is used to store and search for a certain key in a set. Search complexity can be reduced to an ideal level using Trie (key length).

A well-balanced BST will require time proportional to M * log N if we store keys in a binary search tree, where N is the number of keys and M is the max. string length in the tree. The key can be searched in O(M) time using Trie. However, Trie storage requirements are penalized.

Trie is often referred to as a prefix tree or a digital tree.

## Structure of Trie node

Trie has several branches at each node. Each branch stands for a potential key character.  Note that the word node ends at the last node of each key. It is possible to identify a node as the end of a word using the Trie node field isEndOfWord.

The following is an easy structure that can be used to represent the English alphabet's nodes:

 // Trie nodestruct TrieNode{ struct TrieNode *school[ALPHABET_SIZE]; // isEndOfWord is true if the node // represents end of a word bool isEndOfWord;};

## Insert Operation in Trie

Adding a key to Trie is an easy process.

• Each character of the input key is entered as a separate Trie node. Keep in mind that the school is an array of pointers to trie nodes on the next level.
• In array school, the key character acts as an index.
• Create a new node for the key and indicate the word's end for the last node if the input key is new or an extension of an existing key.
• Simply indicate the last node of the input key as the end of the word if it is a prefix of an already existing key in Trie.

Trie depth is determined by the key length.

The construction of a trie using the keys shown in the example below is illustrated in the following image.

## Search Operation in Trie

Key searching is similar to insert operation. However, it moves down after comparing only the characters. The lack of a key in the trie or the end of a string can cause the search to end.

• If the last node's isEndofWord field is true in the first scenario, the key is present in the trie.
• In the second example, because the key is missing from the trie, the search is over before all of the key's characters have been examined.

Note: While Trie's memory needs are O(ALPHABET SIZE * key length * N), where N is the number of keys in Trie, insert and search costs are O(key length).To reduce the trie's memory requirements, there exist effective representations of trie nodes (such as compressed trie, ternary search tree, etc.).

## How is a tree data structure implemented?

• Use the TrieNode() constructor to create a root node.
• Keep a group of strings that need to be inserted into the trie in a vector of strings called arr, for example.
• Using the insert() function to insert all strings into Trie.
• Using the search() method to search strings.

## Trie implementation of above approach

 // C++ implementation of search and insert// operations on Trie#include using namespace std;const int ALPHABET_SIZE = 26;// trie nodestruct TrieNode{ struct TrieNode *school[ALPHABET_SIZE]; // isEndOfWord is true if the node represents // end of a word bool isEndOfWord;};// Returns new trie node (initialized to NULLs)struct TrieNode *getNode(void){ struct TrieNode *pNode = new TrieNode; pNode->isEndOfWord = false; for (int i = 0; i < ALPHABET_SIZE; i++) pNode->school[i] = NULL; return pNode;}// If not present, inserts key into trie// If the key is prefix of trie node, just// marks leaf nodevoid insert(struct TrieNode *root, string key){ struct TrieNode *pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->school[index]) pCrawl->school[index] = getNode(); pCrawl = pCrawl->school[index]; } // mark last node as leaf pCrawl->isEndOfWord = true;}// Returns true if key presents in trie, else// falsebool search(struct TrieNode *root, string key){ struct TrieNode *pCrawl = root; for (int i = 0; i < key.length(); i++) { int index = key[i] - 'a'; if (!pCrawl->school[index]) return false; pCrawl = pCrawl->school[index]; } return (pCrawl->isEndOfWord);}// Driverint main(){ // Input keys (use only 'a' through 'z' // and lower case) string keys[] = {"the", "a", "there", "answer", "any", "by", "bye", "their" }; int n = sizeof(keys)/sizeof(keys); struct TrieNode *root = getNode(); // Construct trie for (int i = 0; i < n; i++) insert(root, keys[i]); // Search for different keys char output[] = {"Not present in trie", "Present in trie"}; // Search for different keys cout<<"the"<<" --- "<

Output

 the --- Present in triethese --- Not present in trietheir --- Present in triethaw --- Not present in trie
write your code here: Coding Playground

## Analysis of the Trie Data Structure's Complexity

 Operation Time Complexity Auxiliary Space Insertion O(n) O(n*m) Searching O(n) O(1)
TrieData StructureC++ ProgrammingComputer Science

### Blog | Board Infinity

At Board Infinity we have authors leading in their profession sharing their insights, ideas and inspiration. Here influential thinkers, creators, makers and doers are found in one place.