Trie Basics

The Idea

A trie spells words out instead of storing them whole. Each edge carries one character, so the path down from the root is a prefix. Words that share a prefix share those nodes.

One flag per node marks "a word ends here" — without it you cannot tell the word car from the prefix inside cart.

Real-World Example

An old library card catalogue: drawers labelled A–C, inside them dividers for the second letter, then the third. Nobody stores the title twice because two books both start with "Ca" — you walk the labels and every book under that divider is a hit.

The Code

root = {}
def insert(word):
    node = root
    for ch in word:                # one node per character
        node = node.setdefault(ch, {})
    node["$"] = True               # "a word ends here"

def search(word):
    node = root
    for ch in word:
        if ch not in node: return False
        node = node[ch]
    return "$" in node             # a bare prefix carries no flag
for w in ["car", "cart", "cat"]: insert(w)
print(search("car"), search("ca"))

root = {}
for word in ["do", "dorm"]:
  node = root
  for ch in word:
      node = node.setdefault(ch, {})
  node["$"] = True
print(sorted(root["d"]["o"]))