Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction:

Trie is a â€˜Tree â€™-based Data Structure mainly used to search words efficiently from an array of Strings or Dictionary. Trie consists of nodes, where each node represents one alphabet, and Trie stores the entire word using these nodes.

Trie is also known as the â€˜Prefix Tree.â€™

Properties of Trie Data Structure:

The root node of the trie is always null.

All the children of nodes are sorted alphabetically.

Every node can have a maximum of 26 children (A to Z).

Every node (except the root) can store one letter of the alphabet

Representation of a Trie Node:

A â€˜TrieNodeâ€™ class consists of the following things:

An array of TrieNodes of size 26. Each index represents one character from 26 English alphabets(A - Z).

A boolean variable â€˜isEndâ€™ representing if this is the last level of your current word.

Source: wikipedia

In the above picture - to, tea, ted, ten, inn, A are stored in the Trie.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Operations in a Trie:

There are three operations we can perform in a Trie:

Insertion of a word

Searching of a word

Deletion of a word

Insertion of a word in a Trie:

Every word starts inserting below the root level.

If the present character node is already present in the Trie, use that node to form your word. But, if there is no present character node at the current level, make a new TrieNode and add its reference to its parentâ€™s TrieNode array. Remember, in the latter case, you need to update the â€˜isEndâ€™ boolean also.

The wordâ€™s length determines the depth of the Trie Tree.

Searching a word in a Trie:

We start comparing the characters of the words with the nodes present in the Trie. Now, there can be the following two cases:

If there is no node present for the current character at any moment, that means the current word is not present in the Trie.

2. Suppose you reach the end of your word. You need to check if â€˜isEndâ€™ for your current node is set to â€˜Trueâ€™ or â€˜False.â€™ If itâ€™s true, that means the word is present in the Trie else no.

In trie, we delete any word in a bottom-up manner consider the following cases:

If the current word is not present in the Trie, your delete operation should not modify the Trie.

If the current word is present as the prefix to another word, just update the â€˜isEndâ€™ boolean variable of the last character node of your current word.

If the current word is not present as the prefix to any word, delete all the references of the characterâ€™s node in the Trie from the bottom until you find a Node with its â€˜isEndâ€™ variable set to true.

Implementation:

#include <bits/stdc++.h> usingnamespacestd; constint aSize = 26; // trie node structTrieNode { structTrieNode* children[aSize]; /* isEndOfWord is true if the node represents end of a word */ bool isEnd; }; // Returns new trie node (initialized to NULLs) struct TrieNode* getNode(void) { structTrieNode* parentNode = newTrieNode; parentNode->isEnd = false; for (int i = 0; i < aSize; i++){ parentNode->children[i] = NULL;

} return parentNode; } /* If the key is not present, this function inserts key into the trie. If the key is prefix of any trie node, just marks leaf node */ voidinsert(struct TrieNode* root, string key) { structTrieNode* curNode = root; for (int i = 0; i < key.length(); i++) { int idx = key[i] - 'a'; if (!curNode->children[idx]){ curNode->children[idx] = getNode(); }

curNode = curNode->children[idx]; } // Mark last node as leaf curNode->isEnd = true; } // This function returns true if the key is present in trie, else false boolsearch(struct TrieNode* root, string key) { structTrieNode* curNode = root; for (int i = 0; i < key.length(); i++) { int idx = key[i] - 'a'; if (!curNode->children[idx]){ returnfalse; }

curNode = curNode->children[idx]; } return (curNode != NULL && curNode->isEnd); } // Returns true if the root has no children, else false boolisEmpty(TrieNode* root) { for (int i = 0; i < aSize; i++){ if (root->children[i]){ returnfalse;

}

}

returntrue; } // Recursive function to delete any key from the given Trie Tree TrieNode* remove(TrieNode* root, string key, int depth = 0) { // If the Trie tree is empty if (!root){ returnNULL;

} // If the last character of the key is getting processed if (depth == key.size()) { /* This node is no more end of any word after removal of the given key */ if (root->isEnd){ root->isEnd = false; } // If given key is not the prefix of any other word if (isEmpty(root)) { delete (root); root = NULL; } return root; } /* If not the last character, recur for the child obtained using the ASCII value */ int index = key[depth] - 'a'; root->children[index] = remove(root->children[index], key, depth + 1); /* If the root does not have any child (it's only child got deleted), and it is not the end of another word. */ if (isEmpty(root) && root->isEnd == false) { delete (root); root = NULL; } return root; } intmain() { /* Input keys (consist of only 'a' through 'z' and int lower case only) */ string keys[] = { "man", "a", "where","answer", "any", "by","bye", "their", "hero", "heroplane" }; int n = sizeof(keys) / sizeof(keys[0]); structTrieNode* root = getNode(); // Construct trie for (int i = 0; i < n; i++){ insert(root, keys[i]); }

All the operations, including Insert, Delete, and Search function works in O(Word_Length) time because we iterate the entire word and keep inserting the node for each node if it is not present. And as soon we iterate the entire word, out word gets inserted, deleted or searched.

Space Complexity:

Implementing trie takes O(Alphabet_Size * numberOfWords * Word_Length) because we are inserting each word in the Trie and each alphabet of the word takes up some memory.

FAQs:

How much time does it take to insert all the words in the Trie Data Structure? Time taken to insert all the words in the Trie is O(N * M) where â€˜Nâ€™ is a total number of words and â€˜Mâ€™ is the largest length of any word because insertion of a single word takes O(M) time where M is the length of a word. Hence inserting â€˜Nâ€™ words will take O(N * M) time.

2. What is the main advantage of Tries? We can insert and search any string in the trie in O(word_length) time.

3. What is the main disadvantage of Trie? Trie takes a lot of memory to store all the Strings.

Key TakeAways:

In this blog, we have covered the following things:

What operations we can perform on a Trie.

How to implement all three functions of Trie.

Time Complexity and Space Complexity of Trie.

If you want to learn more about Heaps and practice some questions requiring you to take your basic knowledge on Heaps a notch higher, you can visit our Guided Path for Trie.

Until then, All the best for your future endeavors, and Keep Coding.