Trie — Tech Epitome

Trie

A tree keyed by character, so shared prefixes are stored once.

Medium3 problems

How do I recognise this pattern?

Autocomplete, or "words starting with" queries.
Many strings share long common prefixes.
Repeated prefix membership tests against a fixed dictionary.
Word-search puzzles where a partial path should be abandoned early.
Finding the longest common prefix across a set.

When it is the wrong tool

Only exact-match lookups are needed — a hash set is simpler and uses less memory.
Suffix rather than prefix queries; build the trie on reversed words, or use a suffix structure.
Few strings, or an alphabet so large that the per-node overhead dominates.

What is it?

Each edge carries a character and each path from the root spells a prefix. Lookup costs time proportional to the length of the word rather than the number of words stored, and every prefix query becomes a simple walk down from the root.

The core idea

The structure pays for itself when prefixes are shared. Its real advantage in search problems is early termination: the moment a path is not a prefix of any word, the entire branch can be abandoned.

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

Python

1class TrieNode:2    def __init__(self):3        self.children = {}4        # A node can be both the end of one word and an interior node of a5        # longer one, so this flag is not the same as "is a leaf".6        self.is_word = False7 8 9class Trie:10    def __init__(self):11        self.root = TrieNode()12 13    def insert(self, word):14        node = self.root15        for char in word:16            if char not in node.children:17                node.children[char] = TrieNode()18            node = node.children[char]19        node.is_word = True20 21    def search(self, word):22        node = self._walk(word)23        return node is not None and node.is_word24 25    def starts_with(self, prefix):26        return self._walk(prefix) is not None27 28    def _walk(self, text):29        node = self.root30        for char in text:31            if char not in node.children:32                return None33            node = node.children[char]34        return node

Common mistakes

Treating a node with no children as the only kind of word end, which breaks whenever one word is a prefix of another.
Sharing a mutable default children map across nodes.
Allocating a fixed 26-slot array per node for a sparse alphabet, wasting most of the memory.
Deleting a word by removing nodes without checking whether another word still needs them.

Problems using Trie

Problem	Difficulty	Role
Shared Label Prefix#142	Easy	Primary
Prefix Tally#143	Medium	Primary
Root Shorthand#144	Medium	Primary