Trie (Prefix Tree)

Time Complexity

Key Points

• Trie nodes store children by character plus a terminal flag
• Insert/search/startsWith operate in O(word length)
• Prefix sharing turns many repeated strings from O(n*m) checks to O(m) checks
• Use tries when constraints ask for many prefix queries on words
• In DFS/word-grid problems, trie + pruning can cut huge search space
• Choose recursive or iterative traversal; recursion gives clean backtracking for grids

Code Examples

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

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

  insert(word) {
    let node = this.root
    for (const ch of word) {
      node.children[ch] = node.children[ch] || new TrieNode()
      node = node.children[ch]
    }
    node.isEndOfWord = true
  }

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

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

const trie = new Trie()
trie.insert('cat')
trie.insert('car')
console.log(trie.search('cat')) // true
console.log(trie.startsWith('ca')) // true

class SuggestionTrieNode {
  constructor() {
    this.children = {}
    this.products = []
  }
}

class ProductSuggester {
  constructor() {
    this.root = new SuggestionTrieNode()
  }

  insert(product) {
    let node = this.root
    for (const ch of product) {
      node.children[ch] = node.children[ch] || new SuggestionTrieNode()
      node = node.children[ch]

      node.products.push(product)
      node.products.sort()
      if (node.products.length > 3) {
        node.products.pop()
      }
    }
  }

  getSuggestions(word) {
    let node = this.root
    const result = []

    for (let i = 0; i < word.length; i++) {
      const ch = word[i]
      if (!node || !node.children[ch]) {
        result.push([])
        node = null
      } else {
        node = node.children[ch]
        result.push([...node.products])
      }
    }

    return result
  }
}

const words = ['apple', 'app', 'apricot', 'banana', 'baton', 'bat']
const suggester = new ProductSuggester()
for (const word of words.sort()) {
  suggester.insert(word)
}

console.log(suggester.getSuggestions('ba'))

Common Mistakes

• Forgetting end-of-word marker leads to false positives on prefixes
• Not handling duplicate words during insert
• Mixing mutable node arrays with object keying incorrectly
• Forgetting to restore board state in trie + DFS grid problems
• Not limiting returned suggestions when using trie-based autocomplete

Interview Tips

• Always start word problems by clarifying alphabet and case rules
• If many strings exist and queries are prefixes, start with a trie
• State complexity in terms of word length and total characters
• For advanced tries, explain how pruning shrinks recursion branching

Practice Problems

Related Concepts