0 Interaction
0 Views
Views
0 Likes

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.

You need to be logged in to participate in this discussion.

×
×
×