Trie in C - Sanfoundry

This is a C Program to implement Trie. A Trie is a very useful (but often ignored) data structure, which can be used to solve a large number of Strings related problems quickly.

Here is source code of the C Program to Implement Trie. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include <stdio.h>
```
```
#include <string.h>
```
```
#include <stdlib.h>
```
```
 
```
```
#define ALPHABET_SIZE 26
```
```
 
```
```
struct node {
```
```
    int data;
```
```
    struct node* link[ALPHABET_SIZE];
```
```
};
```
```
 
```
```
struct node* root = NULL;
```
```
 
```
```
struct node* create_node() {
```

    struct node *q = (struct node*) malloc(sizeof(struct node));

```
    int x;
```
```
    for (x = 0; x < ALPHABET_SIZE; x++)
```
```
        q->link[x] = NULL;
```
```
    q->data = -1;
```
```
    return q;
```
```
}
```
```
 
```
```
void insert_node(char key[]) {
```
```
    int length = strlen(key);
```
```
    int index;
```
```
    int level = 0;
```
```
    if (root == NULL)
```
```
        root = create_node();
```

    struct node *q = root; // For insertion of each String key, we will start from the root

```
 
```
```
    for (; level < length; level++) {
```
```
        index = key[level] - 'a';
```
```
 
```
```
        if (q->link[index] == NULL) {
```

            q->link[index] = create_node(); // which is : struct node *p = create_node(); q->link[index] = p;

```
        }
```
```
 
```
```
        q = q->link[index];
```
```
    }
```

    q->data = level; // Assuming the value of this particular String key is 11

```
}
```
```
 
```
```
int search(char key[]) {
```
```
    struct node *q = root;
```
```
    int length = strlen(key);
```
```
    int level = 0;
```
```
    for (; level < length; level++) {
```
```
        int index = key[level] - 'a';
```
```
        if (q->link[index] != NULL)
```
```
            q = q->link[index];
```
```
        else
```
```
            break;
```
```
    }
```

    if (key[level] == '\0' && q->data != -1)

```
        return q->data;
```
```
    return -1;
```
```
}
```
```
 
```
```
int main(int argc, char **argv) {
```
```
    insert_node("by");
```
```
    insert_node("program");
```
```
    insert_node("programming");
```
```
    insert_node("data structure");
```
```
    insert_node("coding");
```
```
    insert_node("code");
```

    printf("Searched value: %d\n", search("code"));

    printf("Searched value: %d\n", search("geeks"));

    printf("Searched value: %d\n", search("coding"));

    printf("Searched value: %d\n", search("programming"));

```
    return 0;
```
```
}
```

Output:

$ gcc Trie.c
$ ./a.out
 
Searched value: 4
Searched value: -1
Searched value: 6
Searched value: 11

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

« Prev - C Program to Implement Ternary Tree

» Next - C Program to Implement AVL Tree

Related Posts:

Check Computer Science Books
Check Programming Books
Apply for Computer Science Internship
Practice Design & Analysis of Algorithms MCQ
Check Data Structure Books

Recommended Articles: