Tries (Prefix Trees)

March 31, 2026

#trie #prefix-tree #data-structures #autocomplete #string #interviewing

Introduction

A Trie (pronounced “try”) is a tree-like data structure used to store and search strings efficiently. Each node represents a single character, and paths from root to node spell out prefixes. It’s the data structure behind autocomplete, spell checkers, and IP routing tables.

The name comes from “retrieval” — tries are optimized for looking up strings by prefix. Unlike a hash table which gives you O(1) lookup for exact keys, a trie gives you O(m) lookup (where m is the key length) plus the ability to find all keys that share a prefix.

You should be familiar with Binary Trees and Big-O Notation before reading this.

Tries provide O(m) insert, search, and prefix lookup where m is the string length — independent of how many strings are stored. This makes them ideal for autocomplete and dictionary problems.

How a Trie works

Insert: "cat", "car", "card", "dog", "do"

        (root)
       /      \
      c        d
      |        |
      a        o *
      |        |
      t *      g *
      |
      r *
      |
      d *

* = end of word

Each path from root to a * node spells a complete word. The prefix “ca” is shared by “cat”, “car”, and “card”.

Implementation

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._findNode(word);
    return node !== null && node.isEnd;
  }

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

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

const trie = new Trie();
trie.insert('cat');
trie.insert('car');
trie.insert('card');
trie.insert('dog');

console.log(trie.search('car'));       // true
console.log(trie.search('ca'));        // false
console.log(trie.startsWith('ca'));    // true
console.log(trie.startsWith('do'));    // true
console.log(trie.startsWith('bat'));   // false

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_node(word)
        return node is not None and node.is_end

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

    def _find_node(self, s):
        node = self.root
        for char in s:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

trie = Trie()
trie.insert('cat')
trie.insert('car')
trie.insert('card')
trie.insert('dog')

print(trie.search('car'))       # True
print(trie.search('ca'))        # False
print(trie.starts_with('ca'))   # True

import java.util.*;

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

public 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 = findNode(word);
        return node != null && node.isEnd;
    }

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

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

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("cat");
        trie.insert("car");
        trie.insert("card");
        trie.insert("dog");

        System.out.println(trie.search("car"));       // true
        System.out.println(trie.search("ca"));        // false
        System.out.println(trie.startsWith("ca"));    // true
    }
}

Autocomplete with a Trie

The killer feature — find all words that start with a given prefix:

class Trie {
  // ... previous methods

  autocomplete(prefix) {
    const node = this._findNode(prefix);
    if (!node) return [];

    const results = [];
    this._collect(node, prefix, results);
    return results;
  }

  _collect(node, prefix, results) {
    if (node.isEnd) results.push(prefix);

    for (const [char, child] of Object.entries(node.children)) {
      this._collect(child, prefix + char, results);
    }
  }
}

const trie = new Trie();
['cat', 'car', 'card', 'care', 'cargo', 'dog'].forEach(w => trie.insert(w));

console.log(trie.autocomplete('car'));  // ['car', 'card', 'care', 'cargo']
console.log(trie.autocomplete('do'));   // ['dog']
console.log(trie.autocomplete('z'));    // []

Delete from a Trie

class Trie {
  // ... previous methods

  delete(word) {
    this._deleteHelper(this.root, word, 0);
  }

  _deleteHelper(node, word, depth) {
    if (!node) return false;

    if (depth === word.length) {
      if (!node.isEnd) return false;
      node.isEnd = false;
      return Object.keys(node.children).length === 0;
    }

    const char = word[depth];
    const shouldDelete = this._deleteHelper(node.children[char], word, depth + 1);

    if (shouldDelete) {
      delete node.children[char];
      return !node.isEnd && Object.keys(node.children).length === 0;
    }
    return false;
  }
}

Delete is trickier — you need to remove nodes bottom-up, but only if they’re not part of another word’s path.

Complexity analysis

Operation	Time	Space
Insert	O(m)	O(m) per word
Search	O(m)	O(1)
Prefix search	O(m)	O(1)
Autocomplete	O(m + k)	O(k)
Delete	O(m)	O(1)

Where m = length of the string, k = number of results.

Total space: O(n × m) in the worst case where n is the number of words and m is the average length. In practice, shared prefixes reduce this significantly.

Trie vs Hash Table

	Trie	Hash Table
Exact lookup	O(m)	O(m) average
Prefix search	O(m) ✅	Not supported ❌
Ordered iteration	Yes (alphabetical)	No
Space	Higher (node overhead)	Lower
Autocomplete	Natural	Requires scanning all keys

Use a trie when you need prefix operations. Use a hash table when you only need exact key lookup.

Practice problems

Implement Trie (LeetCode 208)
Word Search II (LeetCode 212)
Design Add and Search Words (LeetCode 211)
Replace Words (LeetCode 648)
Longest Word in Dictionary (LeetCode 720)

Table of Contents