Implement insert, search and delete operations on Trie Data structure. Assume that input consist of lowercase letters a-z.

## What is Trie Data Structure?

**Trie** is a tree-based data structure, which is used for efficient re**trie**val of a key in a large data-set of strings. Unlike a binary search tree, where node in the tree stores the key associated with that node, in trie node’s position in the tree defines the key with which it is associated and the key are only associated with the leaves. It is also known as prefix tree as all descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string.

## Trie representation:

There are several ways to represent tries, corresponding to different trade-offs between memory use and speed of the operations. The basic form is that of a linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet (so for the English alphabet, one would store 26 child pointers and for the alphabet of bytes, 256 pointers). Trie node also maintains flag which specifies whether it corresponds to the end of the key or not.

As illustrated in above figure, each key is represented in the trie as a path from the root to the internal node or a leaf.

## Trie Implementation in C

**Insertion** proceeds by walking the trie according to the string to be inserted, then appending new nodes for the suffix of the string that is not contained in the trie. **Searching** also proceeds the similar way by walking the trie according to the string to be search, returning false if the string is not found. **Deletion** is little bit complicated. The idea is to delete the key in bottom up manner using recursion. Special care has to be taken while deleting the key as it can be prefix of another key or its prefix can be another key in Trie.

Below is C implementation of Trie data structure which supports insertion, deletion, and search operations. The implementation currently supports only lowercase English characters (a – z) but it can be easily extended to support any set of characters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 |
#include <stdio.h> // define character size #define CHAR_SIZE 26 // A Trie node struct Trie { int isLeaf; // 1 when node is a leaf node struct Trie* character[CHAR_SIZE]; }; // Function that returns a new Trie node struct Trie* getNewTrieNode() { struct Trie* node = (struct Trie*)malloc(sizeof(struct Trie)); node->isLeaf = 0; for (int i = 0; i < CHAR_SIZE; i++) node->character[i] = NULL; return node; } // Iterative function to insert a string in Trie. void insert(struct Trie* *head, char* str) { // start from root node struct Trie* curr = *head; while (*str) { // create a new node if path doesn't exists if (curr->character[*str - 'a'] == NULL) curr->character[*str - 'a'] = getNewTrieNode(); // go to next node curr = curr->character[*str - 'a']; // move to next character str++; } // mark current node as leaf curr->isLeaf = 1; } // Iterative function to search a string in Trie. It returns 1 // if the string is found in the Trie, else it returns 0 int search(struct Trie* head, char* str) { // return 0 if Trie is empty if (head == NULL) return 0; struct Trie* curr = head; while (*str) { // go to next node curr = curr->character[*str - 'a']; // if string is invalid (reached end of path in Trie) if (curr == NULL) return 0; // move to next character str++; } // if current node is a leaf and we have reached the // end of the string, return 1 return curr->isLeaf; } // returns 1 if given node has any children int haveChildren(struct Trie* curr) { for (int i = 0; i < CHAR_SIZE; i++) if (curr->character[i]) return 1; // child found return 0; } // Recursive function to delete a string in Trie int deletion(struct Trie* *curr, char* str) { // return if Trie is empty if (*curr == NULL) return 0; // if we have not reached the end of the string if (*str) { // recurse for the node corresponding to next character in // the string and if it returns 1, delete current node // (if it is non-leaf) if (*curr != NULL && (*curr)->character[*str - 'a'] != NULL && deletion(&((*curr)->character[*str - 'a']), str + 1) && (*curr)->isLeaf == 0) { if (!haveChildren(*curr)) { free(*curr); (*curr) = NULL; return 1; } else { return 0; } } } // if we have reached the end of the string if (*str == '\0' && (*curr)->isLeaf) { // if current node is a leaf node and don't have any children if (!haveChildren(*curr)) { free(*curr); // delete current node (*curr) = NULL; return 1; // delete non-leaf parent nodes } // if current node is a leaf node and have children else { // mark current node as non-leaf node (DON'T DELETE IT) (*curr)->isLeaf = 0; return 0; // don't delete its parent nodes } } return 0; } // Trie Implementation in C - Insertion, Searching and Deletion int main() { struct Trie* head = getNewTrieNode(); insert(&head, "hello"); printf("%d ", search(head, "hello")); // print 1 insert(&head, "helloworld"); printf("%d ", search(head, "helloworld")); // print 1 printf("%d ", search(head, "helll")); // print 0 (Not present) insert(&head, "hell"); printf("%d ", search(head, "hell")); // print 1 insert(&head, "h"); printf("%d \n", search(head, "h")); // print 1 + newline deletion(&head, "hello"); printf("%d ", search(head, "hello")); // print 0 (hello deleted) printf("%d ", search(head, "helloworld")); // print 1 printf("%d \n", search(head, "hell")); // print 1 + newline deletion(&head, "h"); printf("%d ", search(head, "h")); // print 0 (h deleted) printf("%d ", search(head, "hell")); // print 1 printf("%d\n", search(head, "helloworld")); // print 1 + newline deletion(&head, "helloworld"); printf("%d ", search(head, "helloworld")); // print 0 printf("%d ", search(head, "hell")); // print 1 deletion(&head, "hell"); printf("%d\n", search(head, "hell")); // print 0 + newline if (head == NULL) printf("Trie empty!!\n"); // Trie is empty now printf("%d ", search(head, "hell")); // print 0 return 0; } |

`Output:`

1 1 0 1 1

0 1 1

0 1 1

0 1 0

Trie empty!!

0

**Also see: **

1. C++ Implementation of Trie Data Structure

2. Java Implementation of Trie Data Structure

## Performance of Trie Data Structure –

Time complexity of a Trie data structure for insertion/deletion/search operation is just O(n) where n is key length.

Space complexity of a Trie data structure is O(N*M*C) where N is the number of strings and M is the highest length of the string and C is the size of the alphabet. Please refer below post for memory efficient implementation of the Trie –

Memory efficient Trie Implementation in C++ using Map (Insert, Search and Delete)

## Applications of Trie Data Structure-

There are numerous applications of Trie data structure which take advantage of a trie’s ability to quickly search, insert, and delete entries.

**1. As a replacement for other data structures**

Trie has a number of advantages over binary search trees. It can also be used to replace a hash table as lookup is generally faster in trie even in the worst case. Also there are no collisions of different keys in a trie and a trie can provide an alphabetical ordering of the entries by key.

**2. Autocomplete / Dictionary**

A common application of a trie is storing a predictive text or autocomplete dictionary, such as found on a mobile telephone or search engines. Autocomplete (or word completion) is a feature in which an application predicts the rest of a word a user is typing.

**3. Spell checker**

Spell checker flags words in a document that may not be spelled correctly. Spell checkers are commonly used in word processor (like MS word), email client, search engine, etc.

**4. Lexicographic sorting of a set of keys**

Lexicographic sorting of a set of keys can be accomplished with a simple trie-based algorithm. We initially insert all keys in a trie and then print all keys in the trie by performing pre-order traversal (depth-first traversal), which results in output that is in lexicographically increasing order.

**5.Longest prefix matching**

Longest prefix match algorithm is used by routers in Internet Protocol (IP) networking to select an entry from a forwarding table.

**References: ** https://en.wikipedia.org/wiki/Trie

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

can we do deletion using reference count of each node, insert will increment count, delete will dec count, if zero delete that node.