Imagine you're standing in a massive archive of every word in the English language. If you were looking for the word "Apple," you wouldn't start at the first page of a book and flip through until you found it. Instead, you'd go to the drawer labeled 'A', then find the folder inside labeled 'p', then the sub-folder 'p', 'l', and finally 'e'. Once you hit that final 'e', you've found your destination. The key here is that if you were also looking for "Apply," you wouldn't have to start over at the 'A' drawer; you'd just backtrack one step from 'e' and move into the 'y' folder.

This is exactly how a Trie (pronounced "try," from "retrieval") works. It's a specialized tree where each node represents a single character of a string. Unlike a standard binary search tree, nodes don't store the entire word; they store a piece of the path to the word.

The Anatomy of a Trie Node

To build this in Ruby, we first need a way to represent a single "folder" in our archive. I like to keep the node class lean. It only needs two things: a way to store its children (other characters that follow it) and a way to tell us if a complete word ends at this specific node.

class TrieNode
  attr_accessor :children, :is_end_of_word

  def initialize
    @children = {} # Maps characters to other TrieNode objects
    @is_end_of_word = false
  end
end

I use a Hash for @children because it gives us O(1) average time complexity to jump to the next character. If we're at 'A' and the next letter is 'p', we just look up @children['p'].

Mapping Paths into the Tree

Now we need the actual Trie class to manage these nodes. The core logic happens in the insert method. We start at the root and, for every character in the word, we check if a child node exists for that character. If it doesn't, we create one. It's essentially like building the hallway as you walk through it.

class Trie
  def initialize
    @root = TrieNode.new
  end

  def insert(word)
    current = @root
    word.each_char do |char|
      current.children[char] ||= TrieNode.new
      current = current.children[char]
    end
    current.is_end_of_word = true
  end
end

Notice the ||= operator here. It's a concise way of saying, "If this character isn't already a key in the hash, create a new node for it." Once the loop finishes, we mark the final node as the end of a word. This is crucial because without that flag, we wouldn't be able to tell the difference between the word "App" and the word "Apple" if both were in our Trie.

Searching and Prefix Matching

The real power of a Trie is how fast it handles searches. To find a word, we just follow the path. If we ever hit a character that doesn't exist in the current node's children, we can stop immediately—the word isn't there. I've found that separating "exact search" from "prefix search" makes the code much cleaner.

class Trie
  # ... insert method from above ...

  def search(word)
    node = find_node(word)
    # It's only a match if the node exists AND it's marked as the end of a word
    !node.nil? && node.is_end_of_word
  end

  def starts_with(prefix)
    # We don't care if it's a full word, just that the path exists
    !find_node(prefix).nil?
  end

  private

  def find_node(string)
    current = @root
    string.each_char do |char|
      return nil unless current.children.key?(char)
      current = current.children[char]
    end
    current
  end
end

By extracting find_node into a private helper method, we avoid repeating the loop logic. The starts_with method is what powers the "autocomplete" features you see in search engines; it quickly identifies every possible word that could follow a specific prefix without scanning the entire dataset.

📋 Practical Task

Build a Movie Title Autocomplete System

You are tasked with building a simple autocomplete engine for a movie database. Using the Trie and TrieNode logic from this lesson, implement a new method in the Trie class called suggest(prefix).

Your suggest method should:

• Take a string prefix as an argument.
• Find the node representing the end of that prefix.
• Perform a depth-first search (DFS) or recursive traversal from that node to find all possible complete words that branch off from it.
• Return an array of all words that start with that prefix.

Testing your implementation:

trie = Trie.new
["Inception", "Interstellar", "Iron Man", "The Matrix", "The Godfather"].each { |m| trie.insert(m) }

p trie.suggest("In") 
# Expected output: ["Inception", "Interstellar"]

p trie.suggest("The") 
# Expected output: ["The Matrix", "The Godfather"]

p trie.suggest("Z") 
# Expected output: []