Trie Trees in C++

Yasin Cakal

Trie Trees in C++ are an efficient data structure that allow for the efficient storage and retrieval of data. A trie tree works by storing data in a hierarchical, tree-like structure. In this article, we will discuss the basics of trie trees, how they can be implemented in C++, their time and space complexity, and how they can be used to solve various problems. We will also cover several coding exercises to help you practice and test your understanding of this data structure.

What is a Trie Tree?

A trie tree, also known as a digital tree or prefix tree, is a type of search tree used for storing and retrieving strings. It is an ordered tree data structure that is used to store strings in a sorted way. In a trie tree, each node contains a character from the string. The root node is an empty node, which is the starting point for inserting or retrieving a string.

The trie tree is an efficient data structure for searching for strings, as each node stores a single character and the edges connecting the nodes contain the characters of the string. This allows for fast searching and retrieval of strings, as the characters need not be compared to check for equality.

Implementing a Trie Tree in C++

A trie tree can be implemented in C++ using a class. This class will be used to create nodes in the trie tree. Each node will store a character, a Boolean value indicating whether the node is a leaf node, and a pointer to an array of 26 pointers (one for each alphabetic character). The array of pointers will be used to store the nodes of the tree.

struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 

The following code is an example of a trie tree implemented in C++:

struct TrieNode 
{ 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 

struct Trie 
{ 
    struct TrieNode *root; 
}; 

struct TrieNode * getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
    pNode->isLeaf = false; 
  
    for (int i = 0; i < 26; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
} 

void 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->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    pCrawl->isLeaf = true; 
}

Time and Space Complexity

The time complexity of a trie tree can vary depending on which operation is being performed. Generally speaking, the time complexity of insertion, search, and deletion in a trie tree are all O(M), where M is the length of the string. The time complexity of accessing a node in a trie tree is O(1).

The space complexity of a trie tree is also O(M), where M is the length of the string. This is because each node in the trie tree can contain up to 26 pointers, and each pointer requires a certain amount of storage space.

Using a Trie Tree

Trie trees can be used to solve a variety of problems. For example, they can be used to store and retrieve strings in an efficient manner. They can also be used to check whether a given string is a valid word in a language. Additionally, they can be used to solve problems such as autocomplete, spell-checking, and finding the longest common prefix in a set of strings.

Conclusion

In this article, we discussed the basics of trie trees, how they can be implemented in C++, their time and space complexity, and how they can be used to solve various problems. We also covered several coding exercises to help you practice and test your understanding of this data structure.

Trie trees are an efficient data structure for storing and retrieving strings. They have a time complexity of O(M) for insertion, search, and deletion, and a space complexity of O(M). They can be used to solve a variety of problems, such as autocomplete, spell-checking, and finding the longest common prefix in a set of strings.

Exercises

Write a C++ program to insert a given string into a trie tree.

#include <iostream> 
#include <string> 
  
using namespace std; 
  
struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 
  
struct Trie { 
    struct TrieNode *root; 
}; 
  
struct TrieNode * getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
    pNode->isLeaf = false; 
  
    for (int i = 0; i < 26; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
} 

void 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->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    pCrawl->isLeaf = true; 
} 

int main() 
{ 
    struct TrieNode *root = getNode(); 
  
    string keys[] = {"the", "a", "there", 
                    "answer", "any", "by", 
                     "bye", "their" }; 
    int n = sizeof(keys)/sizeof(keys[0]); 
  
    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 
  
    return 0; 
}

Write a C++ program to search for a given string in a trie tree.

#include <iostream> 
#include <string> 
  
using namespace std; 
  
struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 
  
struct Trie { 
    struct TrieNode *root; 
}; 
  
struct TrieNode * getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
    pNode->isLeaf = false; 
  
    for (int i = 0; i < 26; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
} 

void 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->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    pCrawl->isLeaf = true; 
} 

bool 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->children[index]) 
            return false; 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    return (pCrawl != NULL && pCrawl->isLeaf); 
} 

int main() 
{ 
    struct TrieNode *root = getNode(); 
  
    string keys[] = {"the", "a", "there", 
                    "answer", "any", "by", 
                     "bye", "their" }; 
    int n = sizeof(keys)/sizeof(keys[0]); 
  
    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 
  
    // Search for different keys 
    search(root, "the")? cout << "Yes\n" : 
                         cout << "No\n"; 
    search(root, "these")? cout << "Yes\n" : 
                           cout << "No\n"; 
    return 0; 
}

Write a C++ program to delete a given string from a trie tree.

#include <iostream> 
#include <string> 
  
using namespace std; 
  
struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 
  
struct Trie { 
    struct TrieNode *root; 
}; 
  
struct TrieNode * getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
    pNode->isLeaf = false; 
  
    for (int i = 0; i < 26; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
} 

void 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->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    pCrawl->isLeaf = true; 
} 

bool isLastNode(struct TrieNode* root) 
{ 
    for (int i = 0; i < 26; i++) 
        if (root->children[i]) 
            return 0; 
    return 1; 
} 

bool deleteHelper(struct TrieNode *root, string key, int level, int len) 
{ 
    if (!root) 
        return false; 
  
    if (level == len) { 
        if (root->isLeaf) { 
            root->isLeaf = false; 
            if (isLastNode(root)) { 
                delete(root); 
                root = NULL; 
            } 
  
            return true; 
        } 
    } 
    else { 
        int index = key[level] - 'a'; 
        if (deleteHelper(root->children[index], key, level + 1, len)) { 
            if (isLastNode(root->children[index])) { 
                delete root->children[index]; 
                root->children[index] = NULL; 
            } 
            return true; 
        } 
    } 
    return false; 
} 

bool deleteKey(struct TrieNode *root, string key) 
{ 
    int len = key.length(); 
    if (len > 0) 
        return deleteHelper(root, key, 0, len); 
    return false; 
} 

int main() 
{ 
    struct TrieNode *root = getNode(); 
  
    string keys[] = {"the", "a", "there", 
                    "answer", "any", "by", 
                     "bye", "their" }; 
    int n = sizeof(keys)/sizeof(keys[0]); 
  
    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 
  
    deleteKey(root, "the"); 
    deleteKey(root, "their"); 
  
    return 0; 
}

Write a C++ program to find the longest common prefix in a set of strings using a trie tree.

#include <iostream> 
#include <string> 
  
using namespace std; 
  
struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 
  
struct Trie { 
    struct TrieNode *root; 
}; 
  
struct TrieNode * getNode(void) 
{ 
    struct TrieNode *pNode = new TrieNode; 
    pNode->isLeaf = false; 
  
    for (int i = 0; i < 26; i++) 
        pNode->children[i] = NULL; 
  
    return pNode; 
} 

void 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->children[index]) 
            pCrawl->children[index] = getNode(); 
  
        pCrawl = pCrawl->children[index]; 
    } 
  
    pCrawl->isLeaf = true; 
} 

string commonPrefixUtil(struct TrieNode *root) 
{ 
    string prefix; 
  
    struct TrieNode *pCrawl = root; 
  
    while (pCrawl->isLeaf == false) 
    { 
        bool noChild = true; 
        for (int i = 0; i < 26; i++) 
        { 
            if (pCrawl->children[i]) 
            { 
                prefix.push_back('a' + i); 
                pCrawl = pCrawl->children[i]; 
                noChild = false; 
                break; 
            } 
        } 
  
        if (noChild) 
            break; 
    } 
  
    return prefix; 
} 

string commonPrefix(struct TrieNode *root) 
{ 
    if (root == NULL) 
        return ""; 
  
    return commonPrefixUtil(root); 
} 

int main() 
{ 
    struct TrieNode *root = getNode(); 
  
    string keys[] = {"geeksforgeeks", "geeks", 
                    "geek", "geezer"}; 
    int n = sizeof(keys)/sizeof(keys[0]); 
  
    for (int i = 0; i < n; i++) 
        insert(root, keys[i]); 
  
    cout << "The longest common prefix is " 
         << commonPrefix(root); 
  
    return 0; 
}

Write a C++ program to check whether a given string is a valid word in a language using a trie tree.

#include <iostream> 
#include <string> 
  
using namespace std; 
  
struct TrieNode { 
    char ch; 
    bool isLeaf; 
    struct TrieNode *children[26]; 
}; 
  
struct TrieNode *getNode(char c) { 
    struct TrieNode *node = new TrieNode; 
    node->ch = c; 
    node->isLeaf = false; 
    for (int i = 0; i < 26; i++) 
        node->children[i] = NULL; 
    return node; 
} 
  
void insert(struct TrieNode *root, string &str) { 
    int n = str.length(); 
    struct TrieNode *node = root; 
  
    for (int i = 0; i < n; i++) { 
        int index = str[i] - 'a'; 
        if (node->children[index] == NULL) { 
            node->children[index] = getNode(str[i]); 
            node = node->children[index]; 
        } else { 
            node = node->children[index]; 
        } 
    } 
  
    node->isLeaf = true; 
} 
  
bool search(struct TrieNode *root, string &str) { 
    int n = str.length(); 
    struct TrieNode *node = root; 
  
    for (int i = 0; i < n; i++) { 
        int index = str[i] - 'a'; 
        if (node->children[index] == NULL) 
            return false; 
        node = node->children[index]; 
    } 
  
    return (node != NULL && node->isLeaf); 
} 
  
int main() { 
    struct TrieNode *root = getNode('\0'); 
    string language[] = {"hello", "world", "programming", "coding"}; 
    int n = sizeof(language) / sizeof(language[0]); 
  
    for (int i = 0; i < n; i++) 
        insert(root, language[i]); 
  
    string str = "world"; 
    if (search(root, str)) 
        cout << "Word Found" << endl; 
    else
        cout << "Word Not Found" << endl; 
  
    return 0; 
}

Data Structures and Algorithms with C++

Participants 445