Home › Tries (Prefix Trees) - DSA Fundamentals

Tries (Prefix Trees)

The pattern: A tree where each node represents a character, and paths from root to nodes spell out prefixes. Tries let you search, insert, and check prefixes in O(L) time (L = word length) — regardless of how many words are stored.

Why this matters in interviews: Tries are the go-to for prefix-based problems: autocomplete, spell check, word search in a grid with a dictionary, and IP routing. They replace brute-force string matching with elegant tree traversal.

When to Recognize It

How It Works

Think of a dictionary organized like a tree. The root is empty. Each branch is a letter. To look up “cat,” you follow root → c → a → t. If that path exists and the last node is marked as “end of word,” the word exists. To check the prefix “ca,” you just need the path root → c → a to exist — you don’t care about the end marker.

flowchart TD
    ROOT["root"]:::client
    C["c"]:::service
    A["a"]:::service
    T["t (end)"]:::data
    R["r (end)"]:::data
    D["d"]:::service
    O["o"]:::service
    G["g (end)"]:::data

    ROOT --> C
    ROOT --> D
    C --> A
    A --> T
    A --> R
    D --> O
    O --> G

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

This trie stores: “cat”, “car”, “dog”. Checking “ca” returns true (prefix exists). Checking “cap” returns false (no ‘p’ after ‘a’).

Template Code

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = 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 = True

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

    def _find(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node
class Trie {
    private TrieNode root = new TrieNode();

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

    public boolean search(String word) {
        TrieNode node = find(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix) {
        return find(prefix) != null;
    }

    private TrieNode find(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.children.containsKey(c)) return null;
            node = node.children.get(c);
        }
        return node;
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEnd = false;
}
class Trie {
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    TrieNode* root;

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

    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c))
                node->children[c] = new TrieNode();
            node = node->children[c];
        }
        node->isEnd = true;
    }

    bool search(string word) {
        TrieNode* node = find(word);
        return node && node->isEnd;
    }

    bool startsWith(string prefix) {
        return find(prefix) != nullptr;
    }

private:
    TrieNode* find(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) return nullptr;
            node = node->children[c];
        }
        return node;
    }
};
class TrieNode {
    constructor() {
        this.children = {};
        this.isEnd = false;
    }
}

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

    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.isEnd = true;
    }

    search(word) {
        const node = this._find(word);
        return node !== null && node.isEnd;
    }

    startsWith(prefix) {
        return this._find(prefix) !== null;
    }

    _find(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) return null;
            node = node.children[char];
        }
        return node;
    }
}

Variations

Word Search II (Trie + Backtracking)

Build a trie from the word list. Then DFS on the grid — at each cell, check if the path so far exists in the trie. If not, prune. This avoids repeating the DFS for each word independently.

Autocomplete (DFS from Prefix Node)

Find the prefix node, then DFS from there collecting all words that end at isEnd = True. Optionally sort by frequency if you store counts.

Wildcard Search (Design Add and Search Words)

When the character is . (wildcard), branch into ALL children at that level instead of a specific one. This turns the search into a mini-DFS at each wildcard position.

Complexity

Operation Time Space
Insert O(L) O(L) new nodes
Search O(L) O(1)
Starts With O(L) O(1)
Total space for N words — O(N × L) worst case

Where L = length of the word. In practice, shared prefixes reduce space significantly.

Common Mistakes

Practice Problems

Word Search II and Replace Words require complex grid/string-list I/O — practice these directly on LeetCode.

Key Takeaways