Trie Data Structure - Complete Guide

A Trie (prefix tree) is a tree data structure for efficient string storage and retrieval. This guide covers trie implementation and common problems.

What is a Trie? #

A trie stores strings character by character, with each node representing a character. Common prefixes share the same path.

Trie containing: "cat", "car", "dog"

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

* = end of word

Basic Implementation #

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

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

  insert(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }

    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }

    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;

    for (const char of prefix) {
      if (!node.children.has(char)) {
        return false;
      }
      node = node.children.get(char);
    }

    return true;
  }
}

// Usage
const trie = new Trie();
trie.insert('apple');
console.log(trie.search('apple'));    // true
console.log(trie.search('app'));      // false
console.log(trie.startsWith('app')); // true
trie.insert('app');
console.log(trie.search('app'));      // true

Delete Operation #

class Trie {
  delete(word) {
    this.deleteHelper(this.root, word, 0);
  }

  deleteHelper(node, word, index) {
    if (index === word.length) {
      if (!node.isEndOfWord) {
        return false;  // Word doesn't exist
      }

      node.isEndOfWord = false;

      // Delete node if it has no children
      return node.children.size === 0;
    }

    const char = word[index];

    if (!node.children.has(char)) {
      return false;  // Word doesn't exist
    }

    const childNode = node.children.get(char);
    const shouldDelete = this.deleteHelper(childNode, word, index + 1);

    if (shouldDelete) {
      node.children.delete(char);

      // Delete current node if:
      // - Not end of another word
      // - Has no other children
      return !node.isEndOfWord && node.children.size === 0;
    }

    return false;
  }
}

const trie = new Trie();
trie.insert('apple');
trie.insert('app');
trie.delete('app');
console.log(trie.search('app'));    // false
console.log(trie.search('apple'));  // true

Array Implementation #

Using arrays instead of Maps (for lowercase letters).

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

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

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

  insert(word) {
    let node = this.root;

    for (const char of word) {
      const index = this.charToIndex(char);

      if (!node.children[index]) {
        node.children[index] = new TrieNode();
      }

      node = node.children[index];
    }

    node.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;

    for (const char of word) {
      const index = this.charToIndex(char);

      if (!node.children[index]) {
        return false;
      }

      node = node.children[index];
    }

    return node.isEndOfWord;
  }
}

Autocomplete #

class Trie {
  autocomplete(prefix) {
    let node = this.root;

    // Navigate to prefix node
    for (const char of prefix) {
      if (!node.children.has(char)) {
        return [];
      }
      node = node.children.get(char);
    }

    // Find all words with this prefix
    const results = [];
    this.findAllWords(node, prefix, results);
    return results;
  }

  findAllWords(node, prefix, results) {
    if (node.isEndOfWord) {
      results.push(prefix);
    }

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

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

console.log(trie.autocomplete('car'));
// ['car', 'card', 'cart']

Word Search #

class Trie {
  getAllWords() {
    const words = [];
    this.collectWords(this.root, '', words);
    return words;
  }

  collectWords(node, prefix, words) {
    if (node.isEndOfWord) {
      words.push(prefix);
    }

    for (const [char, childNode] of node.children) {
      this.collectWords(childNode, prefix + char, words);
    }
  }

  countWords() {
    return this.countWordsHelper(this.root);
  }

  countWordsHelper(node) {
    let count = node.isEndOfWord ? 1 : 0;

    for (const childNode of node.children.values()) {
      count += this.countWordsHelper(childNode);
    }

    return count;
  }

  longestCommonPrefix() {
    let prefix = '';
    let node = this.root;

    while (node.children.size === 1 && !node.isEndOfWord) {
      const [char, childNode] = node.children.entries().next().value;
      prefix += char;
      node = childNode;
    }

    return prefix;
  }
}

const trie = new Trie();
trie.insert('flower');
trie.insert('flow');
trie.insert('flight');

console.log(trie.longestCommonPrefix());  // 'fl'
console.log(trie.getAllWords());
// ['flower', 'flow', 'flight']

Wildcard Search #

class Trie {
  searchWithWildcard(word) {
    return this.searchHelper(this.root, word, 0);
  }

  searchHelper(node, word, index) {
    if (index === word.length) {
      return node.isEndOfWord;
    }

    const char = word[index];

    if (char === '.') {
      // Wildcard - try all children
      for (const childNode of node.children.values()) {
        if (this.searchHelper(childNode, word, index + 1)) {
          return true;
        }
      }
      return false;
    } else {
      // Regular character
      if (!node.children.has(char)) {
        return false;
      }
      return this.searchHelper(node.children.get(char), word, index + 1);
    }
  }
}

const trie = new Trie();
trie.insert('bad');
trie.insert('dad');
trie.insert('mad');

console.log(trie.searchWithWildcard('.ad'));  // true
console.log(trie.searchWithWildcard('b..'));  // true
console.log(trie.searchWithWildcard('...'));  // true
console.log(trie.searchWithWildcard('..d'));  // true
console.log(trie.searchWithWildcard('b.d'));  // true

Word Replacement #

class Trie {
  replaceWords(dictionary, sentence) {
    // Build trie from dictionary
    for (const word of dictionary) {
      this.insert(word);
    }

    const words = sentence.split(' ');

    for (let i = 0; i < words.length; i++) {
      const replacement = this.findShortestPrefix(words[i]);
      if (replacement) {
        words[i] = replacement;
      }
    }

    return words.join(' ');
  }

  findShortestPrefix(word) {
    let node = this.root;
    let prefix = '';

    for (const char of word) {
      if (!node.children.has(char)) {
        return null;
      }

      prefix += char;
      node = node.children.get(char);

      if (node.isEndOfWord) {
        return prefix;
      }
    }

    return null;
  }
}

const trie = new Trie();
const dictionary = ['cat', 'bat', 'rat'];
const sentence = 'the cattle was rattled by the battery';

console.log(trie.replaceWords(dictionary, sentence));
// 'the cat was rat by the bat'

Word Dictionary #

Design data structure supporting wildcard search.

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

  addWord(word) {
    let node = this.root;

    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char);
    }

    node.isEndOfWord = true;
  }

  search(word) {
    return this.searchHelper(this.root, word, 0);
  }

  searchHelper(node, word, index) {
    if (index === word.length) {
      return node.isEndOfWord;
    }

    const char = word[index];

    if (char === '.') {
      for (const childNode of node.children.values()) {
        if (this.searchHelper(childNode, word, index + 1)) {
          return true;
        }
      }
      return false;
    }

    if (!node.children.has(char)) {
      return false;
    }

    return this.searchHelper(node.children.get(char), word, index + 1);
  }
}

const dict = new WordDictionary();
dict.addWord('bad');
dict.addWord('dad');
dict.addWord('mad');

console.log(dict.search('pad'));  // false
console.log(dict.search('bad'));  // true
console.log(dict.search('.ad'));  // true
console.log(dict.search('b..'));  // true

Word Search II #

Find all words in a board.

function findWords(board, words) {
  const trie = new Trie();

  // Build trie from words
  for (const word of words) {
    trie.insert(word);
  }

  const result = new Set();
  const rows = board.length;
  const cols = board[0].length;

  function dfs(row, col, node, path) {
    if (row < 0 || row >= rows || col < 0 || col >= cols) {
      return;
    }

    const char = board[row][col];

    if (char === '#' || !node.children.has(char)) {
      return;
    }

    path += char;
    node = node.children.get(char);

    if (node.isEndOfWord) {
      result.add(path);
    }

    const temp = board[row][col];
    board[row][col] = '#';  // Mark visited

    dfs(row + 1, col, node, path);
    dfs(row - 1, col, node, path);
    dfs(row, col + 1, node, path);
    dfs(row, col - 1, node, path);

    board[row][col] = temp;  // Restore
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      dfs(i, j, trie.root, '');
    }
  }

  return Array.from(result);
}

const board = [
  ['o', 'a', 'a', 'n'],
  ['e', 't', 'a', 'e'],
  ['i', 'h', 'k', 'r'],
  ['i', 'f', 'l', 'v']
];

const words = ['oath', 'pea', 'eat', 'rain'];
console.log(findWords(board, words));
// ['oath', 'eat']

Longest Word #

function longestWord(words) {
  const trie = new Trie();

  for (const word of words) {
    trie.insert(word);
  }

  let longest = '';

  function dfs(node, path) {
    for (const [char, childNode] of node.children) {
      if (childNode.isEndOfWord) {
        const newPath = path + char;

        if (newPath.length > longest.length ||
            (newPath.length === longest.length && newPath < longest)) {
          longest = newPath;
        }

        dfs(childNode, newPath);
      }
    }
  }

  dfs(trie.root, '');
  return longest;
}

console.log(longestWord(['w', 'wo', 'wor', 'worl', 'world']));
// 'world'

console.log(longestWord(['a', 'banana', 'app', 'appl', 'ap', 'apply']));
// 'apple'

Palindrome Pairs #

function palindromePairs(words) {
  const trie = new Trie();
  const result = [];

  // Build trie with reversed words
  for (let i = 0; i < words.length; i++) {
    trie.insertWithIndex(words[i].split('').reverse().join(''), i);
  }

  for (let i = 0; i < words.length; i++) {
    const word = words[i];
    const indices = trie.findPalindromePairs(word, i);
    result.push(...indices.map(j => [i, j]));
  }

  return result;
}

Time Complexity #

Operation	Time Complexity	Space Complexity
Insert	O(m)	O(m)
Search	O(m)	O(1)
Delete	O(m)	O(1)
Prefix Search	O(m)	O(1)
Autocomplete	O(m + n)	O(n)

m = word length, n = number of words with prefix

Space Complexity #

Worst case: O(ALPHABET_SIZE * N * M)
N = number of words
M = average word length

Advantages #

Fast prefix search - O(m) vs O(n log n) for binary search
Space efficient for common prefixes - Shared paths
Autocomplete - Natural fit
Sorted iteration - Alphabetical order

Disadvantages #

Space overhead - Each node stores map/array
Cache performance - Poor locality
Memory fragmentation - Many small allocations

Use Cases #

Autocomplete - Search suggestions
Spell checkers - Find similar words
IP routing - Longest prefix match
Dictionary - Word validation
Phone directory - Contact search

Variations #

Compressed Trie (Radix Tree) #

Compress chains of single children.

Regular Trie:      Compressed Trie:
    r                   r
    |                   |
    o                  omance
    |
    m
    |
    a
    |
    n
    |
    c
    |
    e

Ternary Search Trie #

Each node has 3 children: less, equal, greater.

class TSTNode {
  constructor(char) {
    this.char = char;
    this.left = null;
    this.mid = null;
    this.right = null;
    this.isEndOfWord = false;
  }
}

Best Practices #

Use for prefix operations - Main advantage
Consider memory - Large alphabet = more memory
Array vs Map - Arrays faster for small alphabets
Prune unnecessary nodes - Save space
Cache results - For expensive operations
Limit depth - Very long words can be problematic
Consider alternatives - Hash tables for exact match

Tries are powerful for string operations involving prefixes. Master tries for efficient text processing and search functionality.