Trie Data Structure

What is a Trie?

A trie (pronounced "try") is a tree-like data structure used to store associative data structures. It is commonly used for autocomplete and spell-checking. Each node in a trie represents a character of a string, and the path from the root to a node represents a prefix of the string.

Real-World Analogy

Think of a trie as a dictionary where each node represents a letter, and the path from the root to the node forms a word. This structure allows for quick lookup, insertion, and prefix-based queries.

Code Snippets

C++

#include <iostream>
#include <unordered_map>

class TrieNode {
public:
    std::unordered_map<char, TrieNode*> children;
    bool isEndOfWord;
    TrieNode() : isEndOfWord(false) {}
};

class Trie {
private:
    TrieNode root;
public:
    void insert(std::string word) {
        TrieNode *node = &root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }
};

int main() {
    Trie trie;
    trie.insert("cat");
    std::cout << "Inserted 'cat'" << std::endl;
    return 0;
}

Java

import java.util.HashMap;
import java.util.Map;

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEndOfWord;

    TrieNode() {
        children = new HashMap<>();
        isEndOfWord = false;
    }
}

class Trie {
    TrieNode root;

    Trie() {
        root = new TrieNode();
    }

    void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node.children.putIfAbsent(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEndOfWord = true;
    }
}

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        System.out.println("Inserted 'cat'");
    }
}

Python

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

trie = Trie()
trie.insert("cat")
print("Inserted 'cat'")

C

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

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    int isEndOfWord;
} TrieNode;

TrieNode* createNode() {
    TrieNode *node = (TrieNode*)malloc(sizeof(TrieNode));
    for (int i = 0; i < ALPHABET_SIZE; i++) {
        node->children[i] = NULL;
    }
    node->isEndOfWord = 0;
    return node;
}

void insert(TrieNode *root, const char *word) {
    TrieNode *node = root;
    while (*word) {
        int index = *word - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = createNode();
        }
        node = node->children[index];
        word++;
    }
    node->isEndOfWord = 1;
}

int main() {
    TrieNode *root = createNode();
    insert(root, "cat");
    printf("Inserted 'cat'\n");
    return 0;
}