Trie-Based Route Matching Explained

After reading this you will be able to build a segment trie that resolves any URL in time proportional to its depth rather than to the number of registered routes, and to explain exactly why a 2,000-route table stops being a performance problem once you do.

← Back to Route Matching Algorithms

Prerequisites

Core Concept

A linear matcher compares the incoming path against every registered pattern until one matches. The cost is O(n) in the number of routes, and — because each comparison is usually a regular expression — the constant factor is large. A table of 500 routes means up to 500 regex executions per navigation, every navigation.

A segment trie exploits a fact the linear scan ignores: URL paths are hierarchical, and routes that share a prefix share work. Split the path on / and walk a tree of nodes, one node per segment. At each step there are only three possibilities, checked in a fixed order:

  1. A static child whose key equals the segment exactly — an O(1) map lookup.
  2. A dynamic child that accepts any single segment and binds it to a parameter name.
  3. A wildcard child that consumes the remainder of the path.

The cost of a lookup is therefore the number of segments in the URL — its depth, k — multiplied by a tiny constant. Adding routes deepens or widens the tree but does not lengthen any individual walk. A path of four segments costs four steps whether the table holds ten routes or ten thousand.

The static-then-dynamic-then-wildcard ordering is not an implementation convenience; it is the specificity rule, expressed structurally. Because a static child is checked before a dynamic one at each node, /users/new beats /users/:id automatically, with no scoring pass and no sorting of the route table. The related subtleties are covered in route precedence and specificity rules.

A segment trie for a small route table A tree rooted at slash with static children users and reports. The users node has a static child new and a dynamic child colon id, which itself has a static child activity. Matching slash users slash new takes the static branch before the dynamic one. root users static reports static new static — checked first :id dynamic — fallback activity *rest wildcard — checked last At each node: 1 static 2 dynamic 3 wildcard
Specificity is structural: a static child is consulted before a dynamic one at every node, so /users/new never reaches :id.

Implementation

The whole matcher is a node type, an insert function, and a recursive walk.

// TypeScript 5.x — a segment trie router, no dependencies

interface TrieNode<H> {
  /** Exact-match children, keyed by segment text. */
  statics: Map<string, TrieNode<H>>;
  /** Single dynamic child; its name is the parameter it binds. */
  dynamic?: { name: string; node: TrieNode<H> };
  /** Catch-all child; consumes every remaining segment. */
  wildcard?: { name: string; handler: H };
  /** Present when a route terminates exactly here. */
  handler?: H;
}

function createNode<H>(): TrieNode<H> {
  return { statics: new Map() };
}

export function insert<H>(root: TrieNode<H>, pattern: string, handler: H): void {
  const segments = pattern.split("/").filter(Boolean);
  let node = root;

  for (let i = 0; i < segments.length; i++) {
    const segment = segments[i];

    if (segment.startsWith("*")) {
      // A wildcard must be the last segment; everything after it is unreachable.
      node.wildcard = { name: segment.slice(1) || "rest", handler };
      return;
    }

    if (segment.startsWith(":")) {
      const name = segment.slice(1);
      // One dynamic child per node: two would be ambiguous, not more expressive.
      node.dynamic ??= { name, node: createNode<H>() };
      node = node.dynamic.node;
      continue;
    }

    let next = node.statics.get(segment);
    if (!next) {
      next = createNode<H>();
      node.statics.set(segment, next);
    }
    node = next;
  }

  node.handler = handler;
}

The lookup mirrors the insert, with one addition: because a dynamic branch can turn out to be a dead end deeper in the tree, the walk must be able to backtrack to the wildcard.

// TypeScript 5.x — recursive lookup with ordered fallbacks

export interface Match<H> {
  handler: H;
  params: Record<string, string>;
}

export function lookup<H>(
  node: TrieNode<H>,
  segments: string[],
  index = 0,
  params: Record<string, string> = {},
): Match<H> | null {
  if (index === segments.length) {
    return node.handler ? { handler: node.handler, params } : null;
  }

  const segment = segments[index];

  // 1. Static — an O(1) map hit, and the most specific option.
  const staticChild = node.statics.get(segment);
  if (staticChild) {
    const hit = lookup(staticChild, segments, index + 1, params);
    if (hit) return hit; // only return on success, so we can still try dynamic
  }

  // 2. Dynamic — bind the segment and descend.
  if (node.dynamic) {
    const hit = lookup(node.dynamic.node, segments, index + 1, {
      ...params,
      [node.dynamic.name]: decodeURIComponent(segment),
    });
    if (hit) return hit;
  }

  // 3. Wildcard — swallow everything that is left.
  if (node.wildcard) {
    return {
      handler: node.wildcard.handler,
      params: { ...params, [node.wildcard.name]: segments.slice(index).join("/") },
    };
  }

  return null;
}

The if (hit) return hit pattern is what makes this correct rather than merely fast. Committing to the static branch unconditionally would break /users/new/edit when new exists as a static child but has no edit beneath it while :id/edit does. Trying the branch and falling through on failure keeps specificity ordering and completeness.

Lookup cost as the route table grows A comparison chart. Linear regex matching grows in proportion to the number of routes, from ten routes to two thousand. Trie matching stays flat because the cost depends only on the depth of the requested path. Comparisons per lookup as the table grows high 0 linear scan — O(n) trie — O(k), depth only 10 100 400 1000 2000 routes registered
The trie's cost is set by the requested path's depth, so registering more routes widens the tree without lengthening any walk.

Verification 

// TypeScript 5.x — the assertions that matter, runnable under any test runner

const root = createNode<string>();
insert(root, "/users/new", "new-user");
insert(root, "/users/:id", "user-detail");
insert(root, "/users/:id/activity", "user-activity");
insert(root, "/docs/*path", "docs-catch-all");

const run = (p: string) => lookup(root, p.split("/").filter(Boolean));

console.assert(run("/users/new")?.handler === "new-user");        // static wins
console.assert(run("/users/42")?.handler === "user-detail");      // dynamic binds
console.assert(run("/users/42")?.params.id === "42");
console.assert(run("/users/42/activity")?.handler === "user-activity");
console.assert(run("/docs/a/b/c")?.params.path === "a/b/c");      // wildcard swallows
console.assert(run("/users") === null);                            // no partial matches

To confirm the complexity claim rather than assume it, time a lookup against tables of increasing size:

// TypeScript 5.x — a rough but convincing benchmark
for (const size of [10, 100, 1000, 5000]) {
  const trie = createNode<number>();
  for (let i = 0; i < size; i++) insert(trie, `/section-${i}/:id/detail`, i);

  const start = performance.now();
  for (let i = 0; i < 100_000; i++) lookup(trie, ["section-7", "42", "detail"]);
  console.log(size, (performance.now() - start).toFixed(1), "ms");
}

The four timings should be within noise of each other. If they climb with size, a static lookup has become a linear scan somewhere — usually because the statics map was replaced by an array during a refactor.

Backtracking from a dead-end static branch Matching slash users slash new slash edit first descends the static child new, finds no edit beneath it, returns null, and then retries the dynamic child colon id, which does have an edit child. /users/new/edit — why the walk must fall through 1 · try static "new" most specific first no "edit" child beneath it returns null, does not commit 2 · try dynamic ":id" binds id = "new" match: /users/:id/edit specificity preserved AND completeness preserved Committing to the static branch unconditionally would have returned no match at all.
Trying the more specific branch and falling through on failure is what keeps the trie both correctly ordered and complete.

Gotchas

  • Two dynamic children on one node are ambiguous, not expressive. /users/:id and /users/:slug describe the same shape; the second silently wins or loses depending on insertion order. Reject it at insert time.
  • A wildcard is only valid as the final segment. Anything registered after it is unreachable, and failing loudly at insert time saves an afternoon of debugging later.
  • Decode parameters, not the whole path. Decoding before splitting turns an encoded %2F inside a parameter into a segment separator, which changes the match.
  • Empty segments from double slashes. //users splits to ["", "users"] unless you filter; normalise the path once at the entry point rather than defending inside the walk.
  • The trie must be built once. Rebuilding it per navigation converts an O(k) lookup into an O(n) construction and is a surprisingly common regression when route tables move into a component.

FAQ

Is a trie worth it for a small app? Below about fifty routes the difference is unmeasurable, and a regex list is simpler to read. The trie earns its place when the table grows, when routes are registered dynamically by feature modules, or when matching runs on every link render for prefetch decisions.

How do query parameters fit in? They do not — matching operates on the pathname only. Parse the query separately, as described in query string state sync.

Can a trie support regex constraints on a segment? Yes: store an optional test function on the dynamic child and treat a failed test as a non-match so the walk falls through to the wildcard. You keep O(k) as long as there is at most one constrained dynamic child per node.

Why not sort the route table by specificity instead? Sorting fixes precedence but not complexity — you still compare against every pattern. The trie gets both properties from the same structure.

Does this work for nested layouts? Almost: return the chain of nodes visited rather than only the terminal handler, and you have the match chain that nested and layout routing needs.