Trie Data Structure – C Implementation

Trie Tree:
A trie (from retrieval), is a multi-way tree structure useful for storing strings over an alphabet.
It has been used to store large dictionaries of English (say) words in spelling-checking programs and in natural-language “understanding” programs.
A trie tree uses the property that if two strings have a common prefix of length n then these two will have a common path in the trie tree till the length n.

The structure for a node of trie tree is defined as

```struct node
{
bool end_string;
struct node *next_char[26];
};
```

The end_string flag is set if there exists a string that ends at this node.
The next_char[0-26] represents the next character of the string.

The above check function can be modified to create a new function delete_node() that deletes a string present in the trie tree.

Trie tree can be used to find minimum XOR between any two numbers in an array of integers.

The code for trie tree is as follows:

Implementation:

```#include <bits/stdc++.h>

using namespace std;

//each element in the trie tree
struct node
{
bool end_string;
struct node *next_char[26];
};

//to insert the string in the trie tree
void insert(struct node *head, string str)
{
int i, j;
for(i = 0;i < str.size(); ++i){
//if the child node is pointing to NULL
if(head -> next_char[str[i] - 'a'] == NULL){
struct node *n;
//initialise the new node
n = new struct node;
for(j = 0;j < 26; ++j){
n -> next_char[j] = NULL;
}
n -> end_string = 0;
head -> next_char[str[i] - 'a'] = n;
}
//if the child node is not pointing to q
}
//to mark the end_string flag for this string
}

// to check is the string lies in trie tree
bool check(struct node *head, string str)
{
int i;
for(i = 0;i < str.size(); ++i){
if(head -> next_char[str[i] - 'a'] == NULL) return false;
}
//check if the end_string flag is 1
if(head -> end_string == 1) return true;
else return false;
}

int main()
{
int n, m, i;
//n = number of string's to be inserted in trie tree
//m = number of string's to be checked in trie tree

//initialise the new node
for(i = 0;i < 26; ++i){
}

cin >> n;
while(n--){
string str;
cin >> str;
insert(head, str); //to insert the string in the trie tree
}

cin >> m; //number of string's to be checked
while(m--){
string str;
cin >> str;
else cout << "not present\n";
}
return 0;
}
```

Time complexity:

Insert operation takes a time of O(n) where n is the length of string to be inserted.

Space complexity:
The total space taken is O(n * 26) where n is the number of nodes in a tree.