Tries (Prefix Trees) and Their Use Cases

A Trie (derived from retrieval, pronounced "try") is a specialized tree-like search structure optimized for storing and querying strings, particularly when prefix searches are required.

While a Hash Table can look up exact string matches in O(L) time (where L is string length), it cannot efficiently answer prefix queries like: "Find all words beginning with 'app'". A Trie solves this effortlessly.

Anatomy of a Trie Node

In a Trie:

• Nodes do not store entire words.
• Each node represents a single character along a path from the root.
• A boolean flag isEndOfWord marks nodes where a complete valid word terminates.

Copy codeclass TrieNode {
    val children = HashMap<Char, TrieNode>() // or Array of size 26 for 'a'-'z'
    var isEndOfWord = false
}

Copy code               ( Root )
              /        \
            [ c ]      [ a ]
              |          |
            [ a ]      [ p ]
            /   \        |
         [ t*]  [ r*]  [ p*]
                         |
                       [ l ]
                         |
                       [ e*]

Words stored: "cat", "car", "app", "apple"
(* denotes isEndOfWord = true)

Core Operations & Time Complexity

1. Insert (insert("apple"))

Follow character edges starting from root, creating missing nodes along the way. Mark the final node's isEndOfWord = true.

• Time Complexity: O(L), where L is word length.

2. Search (search("app"))

Walk down character edges. If all characters match and the final node has isEndOfWord == true, return true.

• Time Complexity: O(L).

3. Prefix Match (startsWith("ap"))

Walk down character edges for "ap". If you reach the end of the prefix successfully, return true regardless of isEndOfWord.

• Time Complexity: O(L) — completely independent of dictionary size N!

Copy codeclass Trie {
    private val root = TrieNode()

    fun insert(word: String) {
        var curr = root
        for (ch in word) {
            curr = curr.children.computeIfAbsent(ch) { TrieNode() }
        }
        curr.isEndOfWord = true
    }

    fun search(word: String): Boolean {
        val node = findNode(word)
        return node != null && node.isEndOfWord
    }

    fun startsWith(prefix: String): Boolean = findNode(prefix) != null

    private fun findNode(prefix: String): TrieNode? {
        var curr = root
        for (ch in prefix) {
            curr = curr.children[ch] ?: return null
        }
        return curr
    }
}

Production Applications

1. Search Autocomplete & Predictive Text: Google Search, Android virtual keyboard suggestions (Gboard).
2. Spell Checkers: Flagging misspelled words and finding closest edit-distance branches.
3. IP Routing (Longest Prefix Match): Hardware routers use Radix trees (compressed Tries) to route internet packets matching routing table prefixes.

Summary

• Tries organize strings by shared prefixes along root-to-leaf paths.
• Search, insertion, and prefix queries execute in O(L) time, where L is word length.
• The standard foundation for search autocomplete, spellchecking, and IP routing tables.