The Autocomplete Engine

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.

1. Complexity

• Time: O(L) where L is word length. (Faster than Hash Map O(L) due to no hash collision overhead).
• Space: O(N * L * 26). Can be large, but shares prefixes.

2. Interactive: Trie Builder

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

Empty.

3. Implementation

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
}