Trie

trie.cpp

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <utility>
#include <cctype>

#define MAX_SIZE 26

using namespace std;

struct Node
{
    struct Node* children[MAX_SIZE];
    bool isLeaf;
};

Node* createNewNode()
{
    Node* newNode = new Node;
    for(int i=0; i<MAX_SIZE; i++)
    {
        newNode->children[i] = NULL;
    }
    newNode->isLeaf = false;
    return newNode;
}

void insertData(Node* root, string str)
{
    int length = str.length();
    for(int i=0; i<length; i++)
    {
        int character = str[i]-'a';
        if(root->children[character] == NULL)
        {
            root->children[character] = createNewNode();
        }
        root = root->children[character];
    }
    root->isLeaf = true;
}

bool searchData(Node* root, string str)
{
    int length = str.length();
    for(int i=0; i<length; i++)
    {
        int character = str[i]-'a';
        if(root->children[character] == NULL)
        {
            return false;
        }
        root = root->children[character];
    }
    return root->isLeaf;
}

int main()
{
    Node* root = createNewNode();

    insertData(root, "just");
    insertData(root, "some");
    insertData(root, "random");
    insertData(root, "generated");
    insertData(root, "strings");

    printf("%s\n", searchData(root, "some") ? "Found" : "No");
    printf("%s\n", searchData(root, "tests") ? "Found" : "No");
    printf("%s\n", searchData(root, "for") ? "Found" : "No");
    printf("%s\n", searchData(root, "the") ? "Found" : "No");
    printf("%s\n", searchData(root, "strings") ? "Found" : "No");

    return 0;
}