Trie

A detailed explanation of the Trie data structure with examples and use cases.

What is a Trie?

A Trie (pronounced as "try") is a tree-based data structure that stores strings efficiently for fast search, insertion, and deletion. Each node represents a single character, and paths in the tree represent words. Tries are particularly useful for prefix-based problems, such as autocomplete and dictionary lookups.

How a Trie Works

Each node in a Trie contains:

  1. Character: The value stored in the node.
  2. Children: References to child nodes (next characters in the word).
  3. End of Word Marker: A flag to indicate if the node marks the end of a word.

Tries build words character by character, where a single root node branches out for each possible starting character.

Here’s an example of how the Trie looks after inserting the words: cat, cap, bat, and bad.

Key Operations on a Trie

Note

m is the length of the word, p is the length of the prefix and n is the number of child nodes traversed.

Insertion O(m)

Inserts a word character by character. If a character doesn't exist as a child, it creates a new node.

Search O(m)

Checks if a word exists by traversing the tree character by character.

Prefix Matching O(p + n)

Efficiently finds all words starting with a given prefix.

Applications of Tries

Tries are widely used in:

  • Autocomplete systems (like search engines and text editors).
  • Spell checkers and dictionary lookups.
  • IP routing (used in networking).
  • Pattern matching for strings and text processing.

Tries are efficient for operations involving prefixes, making them indispensable in various real-world applications.

Code Examples

Here are examples of basic Trie operations in Python, C++, and Java.

#include <iostream>
#include <unordered_map>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
    }
};

class Trie {
private:
    TrieNode* root;

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

    // Insert a word into the Trie
    void insert(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode();
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true;
    }

    // Search for a word in the Trie
    bool search(string word) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                return false;
            }
            node = node->children[ch];
        }
        return node->isEndOfWord;
    }

    // Check if any word starts with a given prefix
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char ch : prefix) {
            if (!node->children.count(ch)) {
                return false;
            }
            node = node->children[ch];
        }
        return true;
    }
};

// Example usage
int main() {
    Trie trie;
    trie.insert("cat");
    trie.insert("cap");
    trie.insert("bat");
    trie.insert("bad");

    cout << trie.search("cat") << endl; // Output: 1 (true)
    cout << trie.startsWith("ba") << endl; // Output: 1 (true)
    return 0;
}

Problems to Solve

Important Problems on Tries

Resources