Tries (Prefix Trees)

[!NOTE] Stop searching entire lists. Start searching by character.

1. What is a Trie?

A Trie (derived from Retrieval) is a tree-based data structure used to efficiently store and retrieve keys in a dataset of strings. Unlike a Binary Search Tree, nodes in a Trie do not store the key associated with that node. Instead, the path from the root to the node defines the key.

Why not a HashMap?

A HashMap can look up “Apple” in O(1) (Average). But what if you want all words starting with “App”?

• HashMap: Must scan every key. O(N).
• Trie: Just walks down ‘A’ → ‘P’ → ‘P’. O(PrefixLength).

---

2. Interactive: The Autocomplete Engine

Type a word to add it. Type a prefix to search.

Status: Ready.

---

3. Complexity & Constraints

Operation	Time Complexity	Note
Insert	O(L)	L is word length.
Search	O(L)	Independent of total words N!
Space	O(N \times L \times \Sigma)	\Sigma is alphabet size (26).

Mathematical Anchor: The Space Trade-off

Tries are fast but Space Heavy. Space = Total Characters \times Pointer Size. For a dictionary of English, specific branches (like ‘z’) are sparse. Optimization: Radix Tree (Compress single-child chains like ‘A’->’p’->’p’ into one node “App”).

---

4. Implementation (Java)

class TrieNode {
  TrieNode[] children = new TrieNode[26];
  boolean isEndOfWord = false;
}

class Trie {
  TrieNode root = new TrieNode();

  public void insert(String word) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
      int index = c - 'a';
      if (curr.children[index] == null) {
        curr.children[index] = new TrieNode();
      }
      curr = curr.children[index];
    }
    curr.isEndOfWord = true;
  }

  public boolean search(String word) {
    TrieNode curr = root;
    for (char c : word.toCharArray()) {
      int index = c - 'a';
      if (curr.children[index] == null) return false;
      curr = curr.children[index];
    }
    return curr.isEndOfWord;
  }
}