Trie (Prefix Tree) - Notes

Tries store strings by shared prefixes; great for autocomplete and prefix counting.

1
class Node:
2
  def __init__(self):
3
    self.next = {}
4
    self.end = False
5

6
class Trie:
7
  def __init__(self):
8
    self.root = Node()
9
  def insert(self, s):
10
    n = self.root
11
    for c in s:
12
      n = n.next.setdefault(c, Node())
13
    n.end = True
14

15
# usage: insert many words, then traverse by prefix for suggestions