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.

Introduction and implementation of Trie

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.

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

Deleting a Word in a Trie:

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>
using namespace std;

const int aSize = 26;

// trie node
struct TrieNode {
  struct TrieNode* 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)
{
  struct TrieNode* parentNode = new TrieNode;

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
*/
void insert(struct TrieNode* root, string key)
{
  struct TrieNode* 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
bool search(struct TrieNode* root, string key)
{
  struct TrieNode* curNode = root;

  for (int i = 0; i < key.length(); i++) {
  int idx = key[i] - 'a';
  if (!curNode->children[idx]){
  return false;
}

curNode = curNode->children[idx];
}

  return (curNode != NULL && curNode->isEnd);
}

// Returns true if the root has no children, else false
bool isEmpty(TrieNode* root)
{
  for (int i = 0; i < aSize; i++){
  if (root->children[i]){
  return false;

}

  return true;
}

// 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){
  return NULL;

    }

  // 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;
}

int main()
{
  /*
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]);

  struct TrieNode* root = getNode();

  // Construct trie
  for (int i = 0; i < n; i++){
insert(root, keys[i]);
}

  // Search for different keys
  if(search(root, "the")){
  cout << "Yes\n"
}
  else{
  cout << "No\n";
}

  if(search(root, "these"){
  cout << "Yes\n"
}
  else{
  cout << "No\n";
}

remove(root, "heroplane");

  if(search(root, "hero")){
  cout << "Yes\n"
}
  else{
  cout << "No\n";
}

  return 0;
}

Time Complexity:

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.