The Autocomplete Engine

[!NOTE] This module explores the core principles of the Trie (Prefix Tree), deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. Concept Definition

How does Google know you are typing “React” after just “Re…”? It uses a Trie (pronounced “Try”).

A Trie is a tree where:

Nodes are characters.
Paths represent words.
Root is empty.

Key Operations:

Insert: O(L) time, where L is word length.
Search: O(L) time.
Space: O(N * L * 26) in worst case, but compresses common prefixes.

2. Interactive Analysis

Insert words and see how they share branches. Green Node = End of Word.

Empty.

3. Implementation

Java

```java
class TrieNode {
  TrieNode[] children = new TrieNode[26];
  boolean isEnd = false;
}

class Trie {
  TrieNode root;

  public Trie() {
    root = new TrieNode();
  }

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

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

```go
type TrieNode struct {
  Children map[rune]*TrieNode
  IsEnd    bool
}

type Trie struct {
  Root *TrieNode
}

func Constructor() Trie {
  return Trie{Root: &TrieNode{Children: make(map[rune]*TrieNode)}}
}

func (this *Trie) Insert(word string) {
  curr := this.Root
  for _, char := range word {
    if _, ok := curr.Children[char]; !ok {
      curr.Children[char] = &TrieNode{Children: make(map[rune]*TrieNode)}
    }
    curr = curr.Children[char]
  }
  curr.IsEnd = true
}

func (this *Trie) Search(word string) bool {
  curr := this.Root
  for _, char := range word {
    if _, ok := curr.Children[char]; !ok {
      return false
    }
    curr = curr.Children[char]
  }
  return curr.IsEnd
}
```

4. Complexity Analysis

Operation	Time	Space	Notes
Insert	O(L)	O(L * 26)	Creates new nodes for new chars.
Search	O(L)	O(1)	Just traversal.