---
title: "Trie (prefix tree)"
url: https://algopath.pro/patterns/trie
language: en
summary: "Words that share a prefix also share exactly the same path down from the root. A lookup costs only the length of that word."
updated: 2026-08-24
---

# Trie (prefix tree)

Words that share a prefix also share exactly the same path down from the root. A lookup costs only the length of that word.

## 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.

- `root to c` Inserting car and cat. The first character creates one child.
- `c, a, r with a flag` Three nodes and one end flag spell out car.
- `insert cat: c and a exist` The shared prefix is walked, never rebuilt.
- `a to t with a flag` Only one new node is added for the second word.
- `look up ca: no flag` The node exists but is not a word. It is only a prefix.

## When should you use Trie (prefix tree)?

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

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

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

## 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.

```javascript
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(" ");
}
```

## 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.

## JavaScript

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

## Python

```python
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
```

## PHP

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