# Tries (Prefix Trees) — Insert, Search, Prefix Count and Autocomplete

Source: https://skills101.in/learn/dsa/dsa-tries-prefix-trees — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-18.

When you type "ca" in a phone's contact search, it shows "Carol", "Catherine" and "Cathy" at once. The phone is answering a **prefix** question: which stored words **start with** these letters? A hash set can tell you whether one exact word exists, but it cannot answer prefix questions quickly. A **trie** (say "try", from re**trie**val), also called a **prefix tree**, is built exactly for this.

## 1. What a trie looks like

A trie is a tree where:

- the **root** is empty;
- each **edge** (or child node) stands for **one letter**;
- the path from the root to a node spells a **prefix**;
- a node is marked **end of word** if a stored word finishes there.

Here are the words `car, card, care, cat, do, dog`:

![A trie for car, card, care, cat, do and dog; c-a is shared by four words, d-o by two; nodes where a word ends (r, d, e, t, o, g) are green, and each node shows how many words pass through it](https://skills101.in/learn-img/dsa/trie.svg)

Four words share the path `c → a`. They are stored **once**, not four times. Notice that `car` ends at `r`, but `r` still has children (`d` and `e`). That is why we need the **end-of-word** mark: reaching a node does not mean a word ends there.

## 2. Insert and search

Each node keeps a map from letter to child node, an `end` flag, and (for later) a `count` of how many words pass through it.

```python
class TrieNode:
    def __init__(self):
        self.kids = {}        # letter -> TrieNode
        self.end = False      # does a word end here?
        self.count = 0        # how many words pass through this node

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.kids:
                node.kids[ch] = TrieNode()
            node = node.kids[ch]
            node.count += 1
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            if ch not in node.kids:
                return None
            node = node.kids[ch]
        return node

    def search(self, word):              # exact word stored?
        node = self._walk(word)
        return node is not None and node.end

    def starts_with(self, prefix):       # any word with this prefix?
        return self._walk(prefix) is not None

t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
    t.insert(w)
print(t.search("car"), t.search("ca"), t.search("cart"))
print(t.starts_with("ca"), t.starts_with("dx"))
```

```text
True False False
True False
```

`search("ca")` is `False` because no word **ends** at `a`, even though the path exists. `starts_with("ca")` only needs the path.

**Cost.** Insert, search and starts-with all take **O(L)** time, where `L` is the length of the word — no matter how many words are stored. Space is at most the total number of letters across all words, and less when prefixes are shared.

## 3. Prefix count and autocomplete

Because each node stores `count`, "how many words start with this prefix?" is just: walk down the prefix and read the count. For **autocomplete**, walk down the prefix, then do a DFS below that node and collect every word that ends there.

![Table: prefix c has 4 words (car, card, care, cat), ca has 4, car has 3 (car, card, care), do has 2 (do, dog), and x has 0](https://skills101.in/learn-img/dsa/trie-prefix-counts.svg)

```python
class TrieNode:
    def __init__(self):
        self.kids, self.end, self.count = {}, False, 0

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.kids.setdefault(ch, TrieNode())
            node.count += 1
        node.end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.kids.get(ch)
            if node is None:
                return None
        return node

    def count_prefix(self, prefix):
        node = self._walk(prefix)
        return node.count if node else 0

    def autocomplete(self, prefix, limit=10):
        node, out = self._walk(prefix), []
        def dfs(n, word):
            if len(out) == limit:
                return
            if n.end:
                out.append(word)
            for ch in sorted(n.kids):      # sorted: alphabetical suggestions
                dfs(n.kids[ch], word + ch)
        if node:
            dfs(node, prefix)
        return out

t = Trie()
for w in ["car", "card", "care", "cat", "do", "dog"]:
    t.insert(w)
print(t.count_prefix("car"), t.count_prefix("d"), t.count_prefix("z"))
print(t.autocomplete("ca"))
print(t.autocomplete("ca", limit=2))
```

```text
3 2 0
['car', 'card', 'care', 'cat']
['car', 'card']
```

## 4. The same trie in Java

For lowercase English words, an array of 26 children is faster than a map: the child for letter `c` is at index `c - 'a'`.

```java
public class Main {
    static class Node {
        Node[] kids = new Node[26];
        boolean end;
        int count;
    }

    static Node root = new Node();

    static void insert(String w) {
        Node n = root;
        for (char c : w.toCharArray()) {
            int i = c - 'a';
            if (n.kids[i] == null) n.kids[i] = new Node();
            n = n.kids[i];
            n.count++;
        }
        n.end = true;
    }

    static Node walk(String s) {
        Node n = root;
        for (char c : s.toCharArray()) {
            n = n.kids[c - 'a'];
            if (n == null) return null;
        }
        return n;
    }

    public static void main(String[] args) {
        for (String w : new String[]{"car", "card", "care", "cat", "do", "dog"}) insert(w);
        Node a = walk("car"), b = walk("ca"), c = walk("dot");
        System.out.println((a != null && a.end) + " " + (b != null && b.end) + " " + (c != null));
        System.out.println(walk("ca").count + " " + walk("do").count);
    }
}
```

```text
true false false
4 2
```

The array version uses 26 references per node even when most are empty, so it trades memory for speed. A map per node uses less memory when the alphabet is large (for example, Unicode text).

## 5. Trie or hash set?

| Question | Hash set | Trie |
|---|---|---|
| Is this exact word stored? | O(L) on average | O(L) |
| How many words start with "ca"? | must check every word | O(L) |
| List words with a prefix in sorted order | check and sort every word | DFS below one node |
| Memory | one entry per word | shared prefixes, but node overhead |

Typical trie problems: implement a trie, autocomplete or search suggestions, word search on a grid with many words (put the words in a trie so the DFS can stop early), longest common prefix, and replacing words by their shortest root word.

## Common mistakes

- Treating "the path exists" as "the word exists". Always check the `end` flag in `search`.
- Forgetting to increase `count` on every node along the path, so prefix counts come out wrong.
- Using `c - 'a'` when the input can contain capital letters, digits or spaces, which gives a negative or too-large index.
- Building a trie when the problem only ever asks exact-match questions; a hash set is simpler then.

## Quick recap

- A trie stores words letter by letter; words with a common prefix share one path.
- Each node has children, an end-of-word flag and, optionally, a pass-through count.
- Insert, search and starts-with are O(L) for a word of length L.
- Prefix count: walk the prefix, read `count`. Autocomplete: walk the prefix, then DFS.
- Use 26-slot arrays for lowercase letters (fast) or a map per node (flexible).


Practice quiz and free certificate: https://skills101.in/learn/dsa/dsa-tries-prefix-trees