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.

Sources: Wikipedia: Trie, Fredkin (1960), Trie memory

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;
    }
}

class TrieNode {
    children = new Map<string, TrieNode>();
    isEnd = false;
}

class Trie {
    private root = new TrieNode();

    insert(word: string): void {
        let node = this.root;
        for (const c of word) {
            let next = node.children.get(c);
            if (!next) {
                next = new TrieNode();
                node.children.set(c, next);
            }
            node = next;
        }
        node.isEnd = true;
    }

    search(word: string): boolean {
        let node = this.root;
        for (const c of word) {
            const next = node.children.get(c);
            if (!next) return false;
            node = next;
        }
        return node.isEnd;
    }
}

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 c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end

class TrieNode {
    public array $children = [];
    public bool $isEnd = false;
}
class Trie {
    private TrieNode $root;
    public function __construct() { $this->root = new TrieNode(); }
    public function insert(string $word): void {
        $node = $this->root;
        foreach (str_split($word) as $c) {
            $node->children[$c] ??= new TrieNode();
            $node = $node->children[$c];
        }
        $node->isEnd = true;
    }
    public function search(string $word): bool {
        $node = $this->root;
        foreach (str_split($word) as $c) {
            if (!isset($node->children[$c])) return false;
            $node = $node->children[$c];
        }
        return $node->isEnd;
    }
}

    public static class TrieNode {
        public Map<Character, TrieNode> children = new HashMap<>();
        public boolean isEnd = false;
    }

    public static class Trie {
        private final TrieNode root = new TrieNode();

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

        public boolean search(String word) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                node = node.children.get(c);
                if (node == null) return false;
            }
            return node.isEnd;
        }
    }

    public class TrieNode {
        public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
        public bool isEnd = false;
    }

    public class Trie {
        private readonly TrieNode root = new TrieNode();

        public void Insert(string word) {
            var node = root;
            foreach (char c in word) {
                if (!node.children.ContainsKey(c)) node.children[c] = new TrieNode();
                node = node.children[c];
            }
            node.isEnd = true;
        }

        public bool Search(string word) {
            var node = root;
            foreach (char c in word) {
                if (!node.children.TryGetValue(c, out var next)) return false;
                node = next;
            }
            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)?

Use Trie (prefix tree) when the problem statement says “autocomplete or typeahead over many strings”, “longest common prefix among words” or “insert, search, and starts-with on a word set”. A solution built on it usually runs in O(len) per op.

• •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

The signal words of every pattern sit in one table, the algorithm patterns cheat sheet.

What is Trie (prefix tree) confused with?

Trie (prefix tree) is most often confused with Hash set / map, Binary search tree, Matrix word search (grid DFS/backtracking) and DP on strings (word break).

• 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)?

Interview problems solved with Trie (prefix tree) include Implement trie, Replace words, Design add and search words, Word search II, Longest common prefix, Maximum XOR of two numbers and Autocomplete system.

• 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)?

The target complexity of Trie (prefix tree) is O(len) per op.

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