Tries And Prefix Search

A trie stores keys by shared prefixes, making prefix lookup depend mainly on key length rather than the number of stored keys.

Why This Matters

Tries can support autocomplete, routing segments, dictionaries, and prefix policies, but their node overhead can exceed simpler sorted lists or database indexes.

Working Model

Each edge represents a character or token. A terminal marker distinguishes a complete key from a prefix. Unicode normalization and tokenization must be chosen before insertion.

Practical Rules

  • Normalize input consistently.
  • Store terminal state separately from children.
  • Limit result count during traversal.
  • Consider compressed tries or sorted arrays for memory.
  • Use database-native search when data already belongs there.

Failure Modes

  • Treating bytes as user-perceived characters.
  • Returning unlimited autocomplete results.
  • Forgetting that a prefix may also be a complete key.
  • Using a trie for a tiny static list.

Verification

  • Test empty prefixes and exact matches.
  • Test shared prefixes.
  • Test Unicode normalization policy.
  • Compare memory and latency with a sorted-list approach.

What You Should Be Able To Do

After this lesson, you should be able to explain prefix-tree structure, terminal markers, and practical autocomplete tradeoffs, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Practice

Practice: Build A Route Trie

Model route path segments in a trie.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Split normalized paths into segments, store children by segment, mark terminal handlers, and define precedence for literal and parameter segments.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Autocomplete Products

Design bounded product-prefix lookup.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Normalize names, descend through the prefix, collect at most the configured number of terminals, and rank results separately if popularity matters.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.

Practice: Choose A Simpler Option

A project has 80 fixed command names. Decide whether to implement a trie.

Your answer must:

  • state the intended outcome;
  • show the commands, data flow, or implementation shape;
  • identify at least one unsafe alternative;
  • explain how the result will be verified.
Show solution

Prefer a sorted list, map, or direct prefix filter unless measurement proves a trie valuable. The maintenance and memory cost is unlikely to pay off.

The important part is not memorising one command or vendor screen. The solution makes the invariant, failure behavior, and verification evidence explicit.