Tries

Introduction

A Trie (pronounced "try", from the word retrieval) is a tree-like data structure designed to efficiently store and retrieve strings. Think of it like a dictionary where words that share the same beginning are grouped together on the same branch — just like how in a physical dictionary, all words starting with "app" (apple, application, append) are on the same page. Tries are the backbone of features you use every day: autocomplete in search engines, spell checkers, IP routing tables, and even T9 predictive text on old phones.

Problems Addressed by Tries

Imagine you're building a search bar with autocomplete. A user types "pro" and you need to instantly show suggestions like "program", "project", "promise", and "profile". How would you solve this?

The Naive Approach

You could store all words in an array and, for every keystroke, loop through all words checking if each starts with the typed prefix. With 100,000 words and the prefix "pro", you'd scan all 100,000 words every single time. That's O(N × M) where N is the number of words and M is the average word length.

The Trie Approach

With a Trie, you simply walk down the tree following the letters "p" → "r" → "o", and everything below that node is a valid suggestion. The lookup time is O(L) where L is just the length of the prefix — completely independent of how many words are stored. Whether you have 100 words or 10 million, finding all words starting with "pro" takes the same number of steps to reach the prefix node.

Common Use Cases

Autocomplete / typeahead — search engines, IDEs, messaging apps
Spell checking — checking if a word exists in a dictionary
IP routing — longest prefix matching in network routers
Word games — Scrabble solvers, Boggle solvers
DNA sequence matching — bioinformatics pattern searches
Phone directories — contact search by prefix

Core Concepts

How a Trie Works

A Trie is a rooted tree where:

Each node represents a single character
The root node is empty (represents the empty string)
Each path from root to a marked node spells out a stored word
Nodes share common prefixes — the word "cat" and "car" share the nodes for "c" and "a"

This Trie stores the words: cat, cats, car, can, dog, dot. The ✓ symbol indicates nodes where a complete word ends.

Node Structure

Each Trie node typically contains:

A map (or array) of children — one entry per possible character
A boolean flag indicating whether this node marks the end of a valid word
Optionally, additional data (frequency count, the character itself, etc.)

Time and Space Complexity

Operation	Time Complexity	Notes
Insert	O(L)	L = length of the word
Search	O(L)	L = length of the word
Prefix Search	O(L)	L = length of the prefix
Delete	O(L)	L = length of the word
Autocomplete	O(L + K)	K = total chars in all results

Space Complexity: O(N × L × A) in the worst case, where N is the number of words, L is the average length, and A is the alphabet size. In practice, prefix sharing significantly reduces this.

Trie vs HashSet vs Sorted Array

A HashSet can tell you if a word exists in O(L) time — same as a Trie. So why use a Trie?

The key difference is prefix operations. A HashSet cannot efficiently answer "give me all words starting with 'pro'". You'd have to check every word. A Trie navigates directly to the prefix node and collects all descendants.

A sorted array can do prefix matching with binary search, but insertion is O(N) due to shifting elements. Tries give O(L) for both insertion and prefix search.

Implementation

Basic Trie Implementation

javascript

class TrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  /**
   * Inserts a word into the trie.
   * Time: O(L) where L is the word length
   */
  insert(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new TrieNode());
      }
      current = current.children.get(char);
    }
    current.isEndOfWord = true;
  }

  /**
   * Returns true if the exact word exists in the trie.
   * Time: O(L)
   */
  search(word) {
    const node = this._findNode(word);
    return node !== null && node.isEndOfWord;
  }

  /**
   * Returns true if any word in the trie starts with the given prefix.
   * Time: O(L)
   */
  startsWith(prefix) {
    return this._findNode(prefix) !== null;
  }

  /**
   * Navigates to the node representing the last character of the string.
   * Returns null if the path doesn't exist.
   */
  _findNode(str) {
    let current = this.root;
    for (const char of str) {
      if (!current.children.has(char)) {
        return null;
      }
      current = current.children.get(char);
    }
    return current;
  }
}

// --- Demo ---
const trie = new Trie();
const words = ['apple', 'app', 'application', 'apt', 'bat', 'batch', 'bath'];
words.forEach(w => trie.insert(w));

console.log(trie.search('app'));        // true
console.log(trie.search('apple'));      // true
console.log(trie.search('ap'));         // false (prefix exists, but not a complete word)
console.log(trie.startsWith('ap'));     // true
console.log(trie.startsWith('bat'));    // true
console.log(trie.startsWith('bad'));    // false
console.log(trie.search('batman'));     // false

Visualizing Insert Step by Step

Autocomplete Feature

This is arguably the most practical use of a Trie — given a prefix, return all words that start with it.

javascript

class TrieWithAutocomplete extends Trie {
  /**
   * Returns all words that start with the given prefix.
   * Time: O(L + K) where K is total characters in all matching words
   */
  autocomplete(prefix) {
    const node = this._findNode(prefix);
    if (node === null) return [];

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

  /**
   * DFS traversal to collect all complete words below a node.
   */
  _collectWords(node, currentWord, results) {
    if (node.isEndOfWord) {
      results.push(currentWord);
    }

    for (const [char, childNode] of node.children) {
      this._collectWords(childNode, currentWord + char, results);
    }
  }

  /**
   * Returns up to `limit` autocomplete suggestions.
   * More practical for real-world usage.
   */
  autocompleteLimited(prefix, limit = 5) {
    const node = this._findNode(prefix);
    if (node === null) return [];

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

  _collectWordsLimited(node, currentWord, results, limit) {
    if (results.length >= limit) return;

    if (node.isEndOfWord) {
      results.push(currentWord);
    }

    for (const [char, childNode] of node.children) {
      if (results.length >= limit) return;
      this._collectWordsLimited(childNode, currentWord + char, results, limit);
    }
  }
}

// --- Demo ---
const trie = new TrieWithAutocomplete();
const dictionary = [
  'program', 'project', 'promise', 'profile', 'produce',
  'problem', 'process', 'protect', 'provide', 'progress',
  'proper', 'property', 'apple', 'application'
];
dictionary.forEach(w => trie.insert(w));

console.log(trie.autocomplete('pro'));
// ['program', 'project', 'promise', 'profile', 'produce',
//  'problem', 'process', 'protect', 'provide', 'progress',
//  'proper', 'property']

console.log(trie.autocompleteLimited('pro', 3));
// ['program', 'project', 'promise']

console.log(trie.autocomplete('app'));
// ['apple', 'application']

console.log(trie.autocomplete('xyz'));
// []

Delete Operation

Deleting from a Trie is trickier than inserting. You need to be careful not to remove nodes that are part of other words.

javascript

class TrieWithDelete extends Trie {
  /**
   * Deletes a word from the trie.
   * Returns true if the word was found and deleted.
   */
  delete(word) {
    return this._deleteHelper(this.root, word, 0);
  }

  /**
   * Recursive helper: returns true if the parent should delete
   * its reference to the current node.
   */
  _deleteHelper(node, word, depth) {
    // Base case: we've reached the end of the word
    if (depth === word.length) {
      // Word doesn't exist in trie
      if (!node.isEndOfWord) return false;

      // Unmark as end of word
      node.isEndOfWord = false;

      // If node has no children, it can be deleted
      return node.children.size === 0;
    }

    const char = word[depth];
    const childNode = node.children.get(char);

    // Character path doesn't exist
    if (!childNode) return false;

    // Recurse deeper
    const shouldDeleteChild = this._deleteHelper(childNode, word, depth + 1);

    if (shouldDeleteChild) {
      node.children.delete(char);
      // Current node can be deleted if it has no other children
      // and is not the end of another word
      return node.children.size === 0 && !node.isEndOfWord;
    }

    return false;
  }
}

// --- Demo ---
const trie = new TrieWithDelete();
trie.insert('apple');
trie.insert('app');

console.log(trie.search('apple'));  // true
console.log(trie.search('app'));    // true

trie.delete('apple');
console.log(trie.search('apple'));  // false
console.log(trie.search('app'));    // true  (not affected!)

trie.delete('app');
console.log(trie.search('app'));    // false

Counting Words with a Given Prefix

A common interview variant: instead of returning all matching words, just count them.

javascript

class CountingTrie extends Trie {
  constructor() {
    super();
    // We store an extra counter on each node
    this.root = new CountingTrieNode();
  }

  insert(word) {
    let current = this.root;
    for (const char of word) {
      if (!current.children.has(char)) {
        current.children.set(char, new CountingTrieNode());
      }
      current = current.children.get(char);
      current.prefixCount++; // Count how many words pass through this node
    }
    current.isEndOfWord = true;
    current.wordCount++;
  }

  /**
   * Returns the number of words that start with the given prefix.
   * Time: O(L) — no need to traverse all descendants!
   */
  countWordsWithPrefix(prefix) {
    let current = this.root;
    for (const char of prefix) {
      if (!current.children.has(char)) return 0;
      current = current.children.get(char);
    }
    return current.prefixCount;
  }

  countExactWord(word) {
    const node = this._findNode(word);
    return node ? node.wordCount : 0;
  }
}

class CountingTrieNode {
  constructor() {
    this.children = new Map();
    this.isEndOfWord = false;
    this.prefixCount = 0;  // words passing through this node
    this.wordCount = 0;    // words ending at this node
  }
}

// --- Demo ---
const trie = new CountingTrie();
['apple', 'app', 'application', 'apt', 'apply', 'bat', 'batch'].forEach(w => trie.insert(w));

console.log(trie.countWordsWithPrefix('app')); // 4 (apple, app, application, apply)
console.log(trie.countWordsWithPrefix('ap'));   // 5 (+ apt)
console.log(trie.countWordsWithPrefix('b'));    // 2 (bat, batch)
console.log(trie.countWordsWithPrefix('xyz'));  // 0

Wildcard / Pattern Search

Another common interview problem: search with . as a wildcard that matches any character (like in LeetCode 211 - Design Add and Search Words Data Structure).

javascript

class WildcardTrie extends Trie {
  /**
   * Search with '.' wildcards.
   * '.' matches any single character.
   * Example: search('c.t') matches 'cat', 'cut', 'cot'
   */
  searchWithWildcard(pattern) {
    return this._wildcardHelper(this.root, pattern, 0);
  }

  _wildcardHelper(node, pattern, index) {
    if (index === pattern.length) {
      return node.isEndOfWord;
    }

    const char = pattern[index];

    if (char === '.') {
      // Try every child
      for (const [, childNode] of node.children) {
        if (this._wildcardHelper(childNode, pattern, index + 1)) {
          return true;
        }
      }
      return false;
    }

    // Regular character
    if (!node.children.has(char)) return false;
    return this._wildcardHelper(node.children.get(char), pattern, index + 1);
  }
}

// --- Demo ---
const trie = new WildcardTrie();
['cat', 'car', 'cut', 'cot', 'dot', 'dog'].forEach(w => trie.insert(w));

console.log(trie.searchWithWildcard('c.t'));  // true (cat, cut, cot)
console.log(trie.searchWithWildcard('..t'));  // true (cat, cut, cot, dot)
console.log(trie.searchWithWildcard('d.g'));  // true (dog)
console.log(trie.searchWithWildcard('...'));  // true (any 3-letter word)
console.log(trie.searchWithWildcard('c..s')); // false (no 4-letter words starting with c)

Array-Based Trie (Optimized for Lowercase English)

When you know the alphabet is limited (e.g., only lowercase a-z), using an array of size 26 instead of a Map is significantly faster.

javascript

class ArrayTrieNode {
  constructor() {
    this.children = new Array(26).fill(null);
    this.isEndOfWord = false;
  }
}

class ArrayTrie {
  constructor() {
    this.root = new ArrayTrieNode();
  }

  _charIndex(char) {
    return char.charCodeAt(0) - 'a'.charCodeAt(0);
  }

  insert(word) {
    let current = this.root;
    for (const char of word) {
      const idx = this._charIndex(char);
      if (current.children[idx] === null) {
        current.children[idx] = new ArrayTrieNode();
      }
      current = current.children[idx];
    }
    current.isEndOfWord = true;
  }

  search(word) {
    let current = this.root;
    for (const char of word) {
      const idx = this._charIndex(char);
      if (current.children[idx] === null) return false;
      current = current.children[idx];
    }
    return current.isEndOfWord;
  }

  startsWith(prefix) {
    let current = this.root;
    for (const char of prefix) {
      const idx = this._charIndex(char);
      if (current.children[idx] === null) return false;
      current = current.children[idx];
    }
    return true;
  }
}

// This version is ~2-3x faster than the Map version for competitive programming
const trie = new ArrayTrie();
trie.insert('hello');
console.log(trie.search('hello'));     // true
console.log(trie.startsWith('hel'));   // true

Trie Variations

Compressed Trie (Patricia Trie): When a node has only one child, merge them. The word "application" in a standard Trie would need 11 nodes. In a compressed Trie, if no other words share the suffix, it might be stored as just a few nodes with multi-character labels. This saves significant memory.

Ternary Search Trie: Each node has exactly three children — less than, equal to, and greater than. It combines the space efficiency of a Binary Search Tree with the prefix-search capabilities of a Trie. Search for this topic for deeper study.

Suffix Trie: Stores all suffixes of a string. Useful for substring search problems. If you're interested in this area, look into Suffix Trees and Suffix Arrays.

Real-World Architecture: Autocomplete System

Best Practices

Choose the right node type: Use array-based nodes (size 26) for lowercase English-only problems — it's faster. Use Map-based nodes when the alphabet is large or unknown (Unicode, URLs).
Consider memory vs speed tradeoffs: A standard Trie uses more memory than a HashSet. If you only need exact lookups, a HashSet is simpler. Use Tries when you need prefix operations.
Add counts during insertion: If you need prefix counts later, it's much cheaper to maintain them during insertion (O(L) per insert) than to recount by traversal.
Limit autocomplete results: In real applications, always cap the number of results returned. An unbounded autocomplete on a prefix like "a" could return millions of words.
Prefer iterative over recursive for deep Tries: Very long words or large datasets could cause stack overflow with recursive approaches. Consider iterative implementations for production code.
Use compressed Tries for large datasets: If memory is a concern and many words share long prefixes, a Patricia/Compressed Trie significantly reduces node count.
Clean up during delete: When deleting words, prune orphan nodes to prevent memory leaks. Don't just unmark isEndOfWord — remove nodes that are no longer part of any word.
Combine with frequency data: For practical autocomplete systems, store word frequency in the nodes and sort results by popularity rather than alphabetical order.

Hash Tables — Alternative for exact-match lookups; Tries excel at prefix operations where hash tables fall short
Trees — Tries are a specialized form of tree; understanding general tree traversal (DFS, BFS) is essential for Trie operations
Graphs — Tries can be viewed as a directed acyclic graph (DAG) when dealing with suffix links
Heaps — Often combined with Tries to maintain top-K most frequent results in autocomplete systems
Recursion — Many Trie operations (delete, wildcard search) are naturally recursive; understand the call stack mechanics
Depth-First Search — The core traversal strategy for collecting all words under a prefix node

Tests and Challenges

Practice these problems to solidify your understanding of Tries:

LeetCode

208. Implement Trie (Prefix Tree) — The fundamental problem. Implement insert, search, and startsWith.
211. Design Add and Search Words Data Structure — Trie with wildcard search using .
212. Word Search II — Classic hard problem combining Tries with backtracking on a grid
14. Longest Common Prefix — Can be elegantly solved with a Trie
648. Replace Words — Prefix replacement using a Trie
677. Map Sum Pairs — Trie with value aggregation
1268. Search Suggestions System — Autocomplete system design
421. Maximum XOR of Two Numbers in an Array — Bitwise Trie — a clever variant

HackerRank

Contacts — Add contacts and count prefix matches
No Prefix Set — Check if any word is a prefix of another

Tips for Interview Problems

If a problem mentions "prefix", "autocomplete", "dictionary", or "word search", consider a Trie
For grid-based word search problems, Trie + DFS/backtracking is the standard approach
XOR-based problems (find maximum XOR) can use a binary Trie where each bit is a node
When counting prefix matches, augment nodes with counters during insertion rather than traversing at query time

Tries ​

Introduction ​

Problems Addressed by Tries ​

The Naive Approach ​

The Trie Approach ​

Common Use Cases ​

Core Concepts ​

How a Trie Works ​

Node Structure ​

Time and Space Complexity ​

Trie vs HashSet vs Sorted Array ​

Implementation ​

Basic Trie Implementation ​

Visualizing Insert Step by Step ​

Autocomplete Feature ​

Delete Operation ​

Counting Words with a Given Prefix ​

Wildcard / Pattern Search ​

Array-Based Trie (Optimized for Lowercase English) ​

Trie Variations ​

Real-World Architecture: Autocomplete System ​

Best Practices ​

Related Concepts ​

Tests and Challenges ​

LeetCode ​

HackerRank ​

Tips for Interview Problems ​

Tries

Introduction

Problems Addressed by Tries

The Naive Approach

The Trie Approach

Common Use Cases

Core Concepts

How a Trie Works

Node Structure

Time and Space Complexity

Trie vs HashSet vs Sorted Array

Implementation

Basic Trie Implementation

Visualizing Insert Step by Step

Autocomplete Feature

Delete Operation

Counting Words with a Given Prefix

Wildcard / Pattern Search

Array-Based Trie (Optimized for Lowercase English)

Trie Variations

Real-World Architecture: Autocomplete System

Best Practices

Related Concepts

Tests and Challenges

LeetCode

HackerRank

Tips for Interview Problems