A tree where each node is one character and edges spell words. Common prefix = shared path.

Data Flow

insert car, card, care, carb

            root
             |
             c
             |
             a
             |
             r
           / | \
          d* e* b*    (* = end of word)

When to use

• Autocomplete / type-ahead.
• IP routing (longest prefix match).
• Word Search II (trie + backtracking).
• Dictionary check.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False
 
class Trie:
    def __init__(self): self.root = TrieNode()
 
    def insert(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: node.children[ch] = TrieNode()
            node = node.children[ch]
        node.end = True
 
    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children: return False
            node = node.children[ch]
        return node.end
 
    def starts_with(self, prefix):
        node = self.root
        for ch in prefix:
            if ch not in node.children: return False
            node = node.children[ch]
        return True

Pitfalls

• Each node has a dict of up to 26 children — consider array[26] for tight memory.
• search must return node.end; starts_with does not.

Analogy

The contacts autocomplete on your phone: groups every contact’s first 3 letters into a shared tree.

Interview tip: Given millions of words, find ones starting with prefix X — trie beats hashmap on memory and time.