Trie Data Structure: Prefix Trees & Applications

Master trie operations, pattern matching, and autocomplete implementations. This tutorial covers trie structure, insertion/search algorithms, and real-world applications with coding examples.

Trie Usage in Applications (2023)

Autocomplete (40%)

Spell Checkers (30%)

IP Routing (20%)

Other (10%)

1. Trie Fundamentals

Core Properties:

Tree Structure: Each node represents a character
Prefix Sharing: Common prefixes are shared among words
Termination Marker: Special flag indicates word endings
Space Efficiency: Optimal for dictionary storage

Time Complexities:

Operation	Time	Space
Insert	O(L)	O(L)
Search	O(L)	O(1)
Prefix Search	O(P)	O(1)
Delete	O(L)	O(1)

Trie Implementation:


class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = 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.isEndOfWord = true;
  }

  search(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return false;
      node = node.children[char];
    }
    return true;
  }
}

2. Trie Operations & Algorithms

Essential Algorithms:

Autocomplete


function getSuggestions(prefix) {
  let node = this.root;
  for (const char of prefix) {
    if (!node.children[char]) return [];
    node = node.children[char];
  }
  return this._findAllWords(node, prefix);
}

function _findAllWords(node, prefix) {
  let suggestions = [];
  if (node.isEndOfWord) suggestions.push(prefix);
  
  for (const [char, childNode] of Object.entries(node.children)) {
    suggestions.push(...this._findAllWords(childNode, prefix + char));
  }
  return suggestions;
}

Longest Common Prefix


function longestCommonPrefix(words) {
  const trie = new Trie();
  for (const word of words) {
    trie.insert(word);
  }
  
  let lcp = "";
  let node = trie.root;
  while (Object.keys(node.children).length === 1 && !node.isEndOfWord) {
    const char = Object.keys(node.children)[0];
    lcp += char;
    node = node.children[char];
  }
  return lcp;
}

Real-world Applications:

Search Engines: Typeahead suggestions
Contact Lists: Phone number prefix matching
Word Games: Scrabble and Boggle validators
Bioinformatics: DNA sequence matching

3. Advanced Trie Techniques

Specialized Tries:

Compressed Trie

Merge single-child nodes for space efficiency


class CompressedTrieNode {
  constructor() {
    this.children = {}; // key: string, value: node
    this.isEnd = false;
  }
}

// Insertion requires splitting existing edges
// when new words share partial prefixes

Suffix Trie

Stores all suffixes of a text for pattern matching


function buildSuffixTrie(text) {
  const trie = new Trie();
  for (let i = 0; i < text.length; i++) {
    trie.insert(text.slice(i));
  }
  return trie;
}

Trie Optimization Techniques:

Ternary Search Tries: Balance between BST and trie
Double-Array Trie: Memory-efficient representation
Radix Tree: Compressed trie with edge labels
Memory Mapping: Disk-based trie for large datasets

Trie Problem-Solving Cheat Sheet

Problem Type	Approach	Time Complexity
Word Search II	Trie + Backtracking	O(M×4×3^(L-1))
Replace Words	Trie prefix matching	O(N×L)
Concatenated Words	Trie with DFS	O(N×L²)
Maximum XOR	Binary Trie	O(N×32)

4. Trie Variations & Applications

Ternary Search Trie

Combines BST and trie properties


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

class TernarySearchTrie {
  put(key, value) {
    this.root = this._put(this.root, key, value, 0);
  }
  // ... implementation similar to BST but with 3-way branching
}

Radix Tree

Optimized for space with edge compression


class RadixNode {
  constructor() {
    this.children = {}; // key: string prefix
    this.isEnd = false;
  }
}

// Edges store multiple characters
// Requires splitting on insertion conflicts

Binary Trie

For bitwise operations and XOR problems


class BinaryTrieNode {
  constructor() {
    this.children = [null, null]; // 0 and 1
    this.isEnd = false;
  }
}

// Used for maximum XOR of two numbers
// and other bit manipulation problems

Trie Problem-Solving Checklist

✓ Identify prefix-based problems

✓ Consider space-time tradeoffs

✓ Handle Unicode/character sets properly

✓ Optimize with compressed variants for large datasets

DSA Expert Insight: Trie problems appear in 15% of technical interviews, especially in search-related and prefix matching scenarios. Mastering both basic operations and specialized trie variants is crucial for efficient string manipulation problems.

0 Interaction

0 Views

0 Likes