Trie (prefix tree)

How does Trie (prefix tree) work?

The root stands for the empty prefix. It carries no character of its own.

Each edge holds one character. A path from the root spells out a prefix.

Inserting walks the word character by character. A missing child is created along the way.

The last node of a word gets a flag. Without it, a prefix would look like a stored word.

Looking up follows the same path down. A missing child means the word is not there.

A prefix query stops early and reports success. Everything below that node starts with the prefix.

1. root to cInserting car and cat. The first character creates one child.
2. c, a, r with a flagThree nodes and one end flag spell out car.
3. insert cat: c and a existThe shared prefix is walked, never rebuilt.
4. a to t with a flagOnly one new node is added for the second word.
5. look up ca: no flagThe node exists but is not a word. It is only a prefix.

class TrieNode {
    constructor() {
        this.children = new Map();
        this.isEnd = false;
    }
}
class Trie {
    constructor() { this.root = new TrieNode(); }
    insert(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) node.children.set(c, new TrieNode());
            node = node.children.get(c);
        }
        node.isEnd = true;
    }
    search(word) {
        let node = this.root;
        for (const c of word) {
            if (!node.children.has(c)) return false;
            node = node.children.get(c);
        }
        return node.isEnd;
    }
}

A worked example of Trie (prefix tree)

Replace words by their roots

You get a dictionary of roots and a sentence. Replace each word by the shortest root that starts it.

A word with no matching root is left alone.

Insert every root into a trie first.

Then walk each word down the trie. Stop at the first end flag, because that is the shortest root.

function replaceWords(dictionary, sentence) {
    const root = { children: {} };

    for (const word of dictionary) {
        let node = root;
        for (const c of word) {
            node.children[c] = node.children[c] ?? { children: {} };
            node = node.children[c];
        }
        node.end = true; // this node closes a real word
    }

    return sentence
        .split(" ")
        .map((word) => {
            let node = root;
            let prefix = "";

            for (const c of word) {
                if (!node.children[c]) return word; // no root matches
                node = node.children[c];
                prefix += c;
                if (node.end) return prefix; // the first flag is the shortest root
            }

            return word;
        })
        .join(" ");
}

When should you use Trie (prefix tree)?

These phrases in a problem statement point here:

• •autocomplete or typeahead over many strings
• •longest common prefix among words
• •insert, search, and starts-with on a word set
• •match against a large fixed dictionary by prefix

What is Trie (prefix tree) confused with?

• Hash set / map: A map matches whole keys and nothing else. A trie also answers questions by prefix.
• Binary search tree: A search tree compares whole keys to choose a side. A trie walks one character at a time.
• Matrix word search (grid DFS/backtracking): Searching a grid for many words uses a trie to prune. That page is the grid walk itself.
• DP on strings (word break): Word break uses a trie to test each piece. The splitting decision lives in the table.

Common mistakes with Trie (prefix tree)

• Leaving out the end flag

  A stored prefix then cannot be told from a stored word. Every lookup becomes a prefix query.

• Mixing the flag in with the children

  A flag stored under a letter-like key corrupts the tree. Keep children in their own map.

• Building one for a handful of words

  A trie costs memory for every character. Below a few thousand words a set is simpler.

• Assuming a fixed alphabet

  An array of 26 slots breaks on digits or accents. Use a map when the input is not plain letters.

Which interview problems use Trie (prefix tree)?

• Implement trie: Insert, search and the prefix query.
• Replace words: Stop the walk at the first end flag.
• Design add and search words: A dot means try every child at that level.
• Word search II: The trie prunes the grid walk early.
• Longest common prefix: Walk down while there is exactly one child.
• Maximum XOR of two numbers: A binary trie built over the bits.
• Autocomplete system: Rank the words stored under a prefix node.

What is the time and space complexity of Trie (prefix tree)?

O(len) per op

A word of length m costs O(m) to insert or find. Memory is O(total characters) over every word.