Tries (Prefix Trees) — Complete Guide

What is a Trie?

A Trie (pronounced "try", coming from "retrieval"), also known as a Prefix Tree, is a tree-like data structure used to efficiently store and search a dynamic set of strings.

Unlike a Binary Search Tree, nodes in a Trie do not store their own key. Instead, a node's position in the tree defines the key associated with it. All descendants of a node share a common prefix of the string associated with that node.

Trie containing: "cat", "car", "cart", "dog", "dot"

             (root)
            /      \
           c        d
          /          \
         a            o
        / \          / \
       t*  r*       g*  t*
            \
             t*

(* indicates isEndOfWord = true)

Why Use a Trie Over a Hash Table?

While a Hash Table offers O(1) average lookup for exact string matches, a Trie provides several unique advantages:

Trie Node Structure & Basic Operations

Each TrieNode typically contains:

1. children: A map or fixed-size array (e.g., size 26 for lowercase English letters) pointing to child nodes.
2. isEndOfWord: A boolean flag indicating whether the character represents the end of a valid word.

Core Operations & Complexity

• insert(word): O(L) time, where L is the length of the word.
• search(word): O(L) time.
• startsWith(prefix): O(L) time.
• Space Complexity: O(N × L) in the worst case (where N is the number of words and L is average length), but significantly lower when words share common prefixes.

Trie Implementation from Scratch

JavaScript Implementation

javascript
class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    // Inserts a word into the trie
    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    // Returns true if the word is in the trie
    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    // Returns true if there is any word in the trie that starts with the given prefix
    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) return false;
            node = node.children[char];
        }
        return true;
    }
}

// Test
const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true
trie.insert("app");
console.log(trie.search("app"));     // true

Python Implementation

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: str) -> None:
        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

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

C++ Implementation

cpp
#include <iostream>
#include <vector>
#include <string>

class TrieNode {
public:
    TrieNode* children[26];
    bool isEndOfWord;

    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};

class Trie {
private:
    TrieNode* root;

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

    void insert(std::string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) {
                node->children[idx] = new TrieNode();
            }
            node = node->children[idx];
        }
        node->isEndOfWord = true;
    }

    bool search(std::string word) {
        TrieNode* node = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return node->isEndOfWord;
    }

    bool startsWith(std::string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (!node->children[idx]) return false;
            node = node->children[idx];
        }
        return true;
    }
};

Solved Problem 1: Design Add and Search Words Data Structure 🟡 Medium

Problem: Design a data structure that supports adding new words and finding if a string matches any previously added string. The search query can contain dots . where . can be matched with any letter.

Example:

WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // -> false
wordDictionary.search("bad"); // -> true
wordDictionary.search(".ad"); // -> true
wordDictionary.search("b.."); // -> true

Approach: Use a Trie. When encountering a ., recursively explore all non-null child nodes at the current level.

javascript
class WordDictionary {
    constructor() {
        this.root = new TrieNode();
    }

    addWord(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        return this._dfs(word, 0, this.root);
    }

    _dfs(word, index, node) {
        if (!node) return false;
        if (index === word.length) return node.isEndOfWord;

        const char = word[index];

        if (char === '.') {
            // Check all possible child branches
            for (const key in node.children) {
                if (this._dfs(word, index + 1, node.children[key])) {
                    return true;
                }
            }
            return false;
        } else {
            if (!node.children[char]) return false;
            return this._dfs(word, index + 1, node.children[char]);
        }
    }
}

Time Complexity: addWord: O(L), search: O(L) for exact words, up to O(26^L) for queries with multiple wildcards.

Solved Problem 2: Word Search II (Grid Backtracking + Trie) 🔴 Hard

Problem: Given an m x n board of characters and a list of strings words, return all words on the board. Each word must be constructed from letters of sequentially adjacent cells (horizontally or vertically).

Why Trie is Essential Here: If you run standard DFS/backtracking for every word independently, it causes massive redundant grid traversals. By inserting all words into a Trie, you can backtrack through the grid once and check prefix validity in O(1) time at each step!

javascript
function findWords(board, words) {
    const root = new TrieNode();

    // 1. Build Trie from words list
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) node.children[char] = new TrieNode();
            node = node.children[char];
        }
        node.word = word; // Store full word at leaf node for easy retrieval
    }

    const result = [];
    const rows = board.length;
    const cols = board[0].length;

    // 2. DFS Backtracking
    function dfs(r, c, parentNode) {
        const char = board[r][c];
        const currNode = parentNode.children[char];

        if (!currNode) return;

        // Found a word!
        if (currNode.word) {
            result.push(currNode.word);
            currNode.word = null; // Avoid duplicate entries
        }

        // Mark visited
        board[r][c] = '#';

        const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
        for (const [dr, dc] of dirs) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] !== '#') {
                dfs(nr, nc, currNode);
            }
        }

        // Backtrack
        board[r][c] = char;
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (root.children[board[r][c]]) {
                dfs(r, c, root);
            }
        }
    }

    return result;
}

Real-World Usages

1. Search Engine Autocomplete & Suggestions: When typing into Google or a browser search bar, a Trie quickly identifies all words matching the prefix entered so far.
2. IP Routing / Longest Prefix Match: Routers use specialized Tries (such as Radix Trees) to match IP packet destination addresses against subnet masks.
3. Spell Checkers & Dictionary Apps: Instantly checks word validity and suggests corrections based on partial prefix matching.
4. Text Prediction (T9 Keypads): Old mobile keypads used Tries to convert sequence of keypresses (e.g. 2-7-7-5-3) to valid dictionary words ("apple").

Frequently Asked Questions

Q: What is the space complexity of a Trie?
A: In the worst case where no words share prefixes, it takes O(N × L × Σ) space, where N is the number of words, L is average length, and Σ is the alphabet size (e.g. 26). However, in practical applications with overlapping prefixes, Tries compress prefix storage significantly.

Q: What is the difference between a Trie and a Radix Tree (Patricia Trie)?
A: A standard Trie has nodes for single characters, even if a path has no branching. A Radix Tree compresses single-child node chains into a single edge containing a string segment, dramatically reducing memory overhead.

Q: Can Tries be used for Bitwise / XOR operations?
A: Yes! A Bitwise Trie stores binary representations (bits 0 and 1) of integers. This is widely used to solve maximum XOR pair problems in O(32 × N) time.