Skip to main content
πŸ—οΈ Data Structure Builds

What you're building

A Trie (prefix tree) β€” a tree where each node represents one character, and every path from root to a marked leaf spells out a word. Tries power:

  • Search box autocomplete (Google, VS Code)
  • Spell-checkers
  • IP routing tables
  • Autocorrect on your phone keyboard

Requirements

  • insert(word) β€” add a word to the trie
  • search(word) β€” return true if the exact word was inserted
  • startsWith(prefix) β€” return true if any inserted word begins with prefix
  • autocomplete(prefix) β€” return an array of all inserted words that start with prefix (any order, max 10 results)

Stretch goals

  • Add a delete(word) method that removes a word without breaking other words sharing its prefix
  • Weight words by insertion frequency and return autocomplete results sorted by frequency

What this proves

You can implement tree traversal, recursive DFS, and understand a core data structure used in production search infrastructure.

⚑ 50 XP
solution.jsRuns in your browser
Loading editor…
Tests4 to pass
search finds inserted words
startsWith prefix matching
autocomplete returns all words with prefix
autocomplete returns empty for unknown prefix

Run your code to check these.