In this problem you will implement a data structure called a

In this problem, you will implement a data structure called a ‘trie’ as a ternary tree. Each node in a ternary tree can have at most three children nodes. The key inside each node is a character. The children of each node are the following:
•   left: contains a key that is less than the current node’s key, or null
•   equal: contains a key that is the next character in the string being stored, or null
•   right: contains a key that is more than the current node’s key, or null
Here is an example, on how to create a trie to store a set of strings:
Strings: {beth, bob, james, carl, tom, terry, luke, barb, bailey, bernie, barney}
Insert string ”beth”. Initially root is empty. So, ‘b’ is inserted as the root, ‘e’ is inserted as equal-child of ‘b’, ‘t’ is inserted as equal-child of ‘e’, and, lastly, ‘h’ is inserted as equal-child of ‘t’.

Next, for the string “bob”, we start at root of tree, ‘b’. The first character of bob(‘b’) is already the root, so we do not insert another node for ‘b’. We go to the second character of bob (‘o’). To insert ‘o’, we go down the equal-child of ‘b’ (which is ‘e’). ‘o’ > ‘e’, so we go down right subtree of ‘e’. Because right subtree of ‘e’ is null, we insert ‘o’ as right child of ‘e’. After that, We go to the third character of bob (‘b’); ‘b’ becomes equal-child of ‘o’.

Next, we insert string “james”; we start again at root of tree, which is ‘b’. ‘j’ > ‘b’. So, we go down right subtree of ‘b’. Because right child of ‘b’ is null, we insert ‘j’ a right-child of ‘b’. ‘a’, ‘m’, ‘e’ and ‘s’ are then inserted equal-children (successively) below ‘j’

One more example, insert ‘carl’. We start at the root of the tree, which is ‘b’. ‘c’ > ‘b’, so we go down right subtree of ‘b’ and reach ‘j’. ‘c’< ‘j’, so we go down left subtree of ‘j’. This left subtree of ‘j’ is null, and we insert ‘c’ as left child of ‘j’. ‘a’, ‘r’ and ‘l’ are then inserted as equal-children (successively) below ‘c’

The rest of the strings are inserted below

To lookup or search for a string in a trie, you start at the root. Depending on the character of the string being searched for go down the left, equal or right child at each node. Note that to find a string successfully, the number of equal edges traversed should be equal to the number of characters in the string less 1.

Solution

The C implementation of trie data structure is as follows.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define ARRAY_SIZE(arr) sizeof(arr)/sizeof(arr[0])
#define ALPHABET_SIZE (26)

#define CHAR_TO_INDEX(c) ((int)c - (int)\'a\')
struct TrieNode
{
struct TrieNode *child[ALPHABET_SIZE];

bool isLeaf;
};

struct TrieNode *getNode(void)
{
struct TrieNode *tNode = NULL;

tNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

if (tNode)
{
int i;

tNode->isLeaf = false;

for (i = 0; i < ALPHABET_SIZE; i++)
tNode->child[i] = NULL;
}

return tNode;
}
void insert(struct TrieNode *root, const char *key)
{
int l;
int length = strlen(key);
int index;

struct TrieNode *tc = root;

for (l = 0; l < length; l++)
{
index = CHAR_TO_INDEX(key[l]);
if (!tc->child[index])
tc->child[index] = getNode();

tc = tc->child[index];
}

// mark last node as leaf
tc->isLeaf = true;
}

bool find(struct TrieNode *root, const char *key)
{
int l;
int length = strlen(key);
int index;
struct TrieNode *tc = root;

for (l = 0; l < length; l++)
{
index = CHAR_TO_INDEX(key[l]);

if (!tc->child[index])
return false;

tc = tc->child[index];
}

return (tc != NULL && tc->isLeaf);
}
int main()
{
char keys[][8] = {\"bob\", \"james\", \"the\",
\"carl\"};

char result[][40] = {\"Not present in trie\", \"Present in trie\"};


struct TrieNode *root = getNode();

int i;
for (i = 0; i < ARRAY_SIZE(keys); i++)
insert(root, keys[i]);

printf(\"%s is %s\ \", \"bob\", result[find(root, \"bob\")] );
printf(\"%s is %s\ \", \"james\", result[find(root, \"james\")] );
printf(\"%s is %s\ \", \"carl\", result[find(root, \"car\")] );
printf(\"%s is %s\ \", \"the\", result[find(root, \"the\")] );

return 0;
}

The runtime required for the implementation is O(N) .