TrieRouter - Hono

Overview

The TrieRouter uses a trie (prefix tree) data structure to organize and match routes. It supports all possible path patterns and provides consistent, predictable performance characteristics.

How It Works

The TrieRouter organizes routes in a tree structure where:

Each node represents a path segment
Static segments are stored as direct children
Dynamic parameters (:param) are stored as pattern nodes
Wildcards (*) are handled as special pattern nodes
Route matching traverses the tree depth-first

Algorithm Details

Tree Structure: Routes split by / into segments, forming a prefix tree
Pattern Matching: Each node can have multiple patterns (:param, :param{regex}, *)
Parameter Extraction: Parameters collected during tree traversal
Scoring System: Routes scored by insertion order to handle ambiguous patterns
Multi-path Search: Explores multiple branches simultaneously for wildcard matching

Performance Characteristics

Static Routes

O(n) - Tree traversal by path segments

Dynamic Routes

O(n × m) - n segments × m patterns per node

Build Time

O(1) - Routes inserted immediately

Memory

Medium - Tree grows with unique path prefixes

When to Use

✅ Best For

Applications requiring support for all path patterns
Routes with complex parameter patterns and wildcards
Applications adding routes dynamically at runtime
Routes with duplicate parameter names (less restrictive)
Development and testing environments
Small to medium-sized applications (< 100 routes)

❌ Not Recommended For

Large applications with 1000+ routes (consider RegExpRouter)
Maximum performance requirements (use RegExpRouter)
Edge environments with strict memory limits

Configuration

To use the TrieRouter, specify it when creating your Hono instance:

import { Hono } from 'hono'
import { TrieRouter } from 'hono/router/trie-router'

const app = new Hono({ router: new TrieRouter() })

Usage Examples

Basic Routing

import { Hono } from 'hono'
import { TrieRouter } from 'hono/router/trie-router'

const app = new Hono({ router: new TrieRouter() })

// Static routes
app.get('/', (c) => c.text('Home'))
app.get('/about', (c) => c.text('About'))
app.get('/contact', (c) => c.text('Contact'))

// Dynamic routes
app.get('/users/:id', (c) => {
  const id = c.req.param('id')
  return c.json({ userId: id })
})

// Nested parameters
app.get('/posts/:postId/comments/:commentId', (c) => {
  const { postId, commentId } = c.req.param()
  return c.json({ postId, commentId })
})

Complex Parameter Patterns

// Pattern with RegExp validation
app.get('/users/:id{[0-9]+}', (c) => {
  const id = c.req.param('id')
  return c.json({ userId: id })
})

// Multiple patterns in one route
app.get('/files/:filename{.+\\.(jpg|png|gif)}', (c) => {
  const filename = c.req.param('filename')
  return c.json({ file: filename })
})

// Advanced RegExp patterns
app.get('/api/:version{v[1-9]+}/:resource', (c) => {
  const { version, resource } = c.req.param()
  return c.json({ version, resource })
})

Optional Parameters

// Optional trailing segment
app.get('/api/users/:id?', (c) => {
  const id = c.req.param('id')
  if (id) {
    return c.json({ user: id })
  }
  return c.json({ users: 'all' })
})

// Multiple optional segments
app.get('/docs/:section?/:page?', (c) => {
  const { section, page } = c.req.param()
  return c.json({ section: section || 'home', page: page || 'index' })
})

Wildcard Routes

// Catch-all wildcard
app.get('/static/*', (c) => {
  return c.text('Static file handler')
})

// Wildcard in the middle of a path
app.get('/api/*/status', (c) => {
  return c.json({ status: 'ok' })
})

// Multiple wildcards
app.get('/files/*/versions/*', (c) => {
  return c.text('File version handler')
})

Advanced Patterns

// Combining parameters and wildcards (supported by TrieRouter!)
app.get('/users/:id/*', (c) => {
  const id = c.req.param('id')
  return c.text(`User ${id} sub-resource`)
})

// Complex nested structures
app.get('/:tenant/api/:version/resources/:id', (c) => {
  const { tenant, version, id } = c.req.param()
  return c.json({ tenant, version, resourceId: id })
})

// Pattern matching with lookahead
app.get('/items/:id{[a-z0-9-]+}', (c) => {
  const id = c.req.param('id')
  return c.json({ itemId: id })
})

How Matching Works

Tree Traversal

// Example route structure:
app.get('/api/users/:id', handler1)
app.get('/api/posts/:id', handler2)
app.get('/api/*', handler3)

// Creates a trie:
// root
//  └─ api
//      ├─ users
//      │   └─ :id → handler1
//      ├─ posts
//      │   └─ :id → handler2
//      └─ * → handler3

// Request: GET /api/users/123
// 1. Start at root
// 2. Match 'api' → traverse to 'api' node
// 3. Match 'users' → traverse to 'users' node
// 4. Match '123' against ':id' pattern → found handler1
// 5. Also check wildcard → found handler3
// 6. Return both handlers (middleware + main handler)

Pattern Priority

The TrieRouter uses a scoring system to handle multiple matching routes:

app.get('/api/users', handler1)      // Static: highest priority
app.get('/api/:resource', handler2)  // Dynamic: medium priority
app.get('/api/*', handler3)          // Wildcard: lowest priority

// Request: GET /api/users
// Returns: [handler1, handler3] (sorted by score)

Advanced Features

Dynamic Route Registration

Unlike RegExpRouter, TrieRouter supports adding routes after the application has started handling requests:

const app = new Hono({ router: new TrieRouter() })

// Initial routes
app.get('/api/v1/users', listUsers)

// Start handling requests
app.fire()

// Add new routes dynamically (supported!)
app.get('/api/v2/users', listUsersV2)

Multi-Handler Resolution

TrieRouter can return multiple handlers for a single path when wildcards or patterns overlap:

app.use('/api/*', authMiddleware)
app.get('/api/users', getUsers)

// GET /api/users returns: [authMiddleware, getUsers]

Parameter Validation

// Use RegExp patterns for parameter validation
app.get('/users/:id{[0-9]+}', (c) => {
  // id is guaranteed to be numeric
  const id = parseInt(c.req.param('id'))
  return c.json({ userId: id })
})

// Invalid requests won't match
// GET /users/abc → 404
// GET /users/123 → matches

Internal Architecture

Node Structure

class Node<T> {
  #methods: Record<string, HandlerSet<T>>[]  // Handlers for this node
  #children: Record<string, Node<T>>         // Child nodes (segments)
  #patterns: Pattern[]                        // Dynamic patterns
  #order: number                              // Insertion order for scoring
}

Insert Process

// Conceptual insert flow
Split path into segments: '/api/users/:id' → ['api', 'users', ':id']
Traverse/create nodes for each segment
Identify patterns (static, :param, :param{regex}, *)
Store handler at final node with method and score
Track possible parameter keys for this route

Search Process

// Conceptual search flow
1. Split request path into segments
2. Start with root node
3. For each segment:
   a. Check static child nodes
   b. Check pattern nodes
   c. Check wildcard nodes
   d. Collect matching handlers
4. Sort handlers by score
5. Return [handlers, params]

Comparison with Other Routers

Feature	TrieRouter	RegExpRouter	LinearRouter
All patterns	✅ Yes	❌ Limited	✅ Yes
Static routes	O(n)	O(1)	O(n)
Dynamic routes	O(n × m)	O(1)	O(n)
Memory usage	Medium	High	Low
Dynamic registration	✅ Yes	❌ No	✅ Yes
Complex patterns	✅ Yes	⚠️ Some	✅ Yes

Performance Tips

Optimize TrieRouter performance:

Group similar routes - Routes with common prefixes share tree nodes
Limit pattern complexity - Simple patterns match faster than complex RegExp
Avoid excessive wildcards - Each wildcard adds branches to explore
Use specific patterns - /users/:id{[0-9]+} is faster than /users/:id

Performance Example

// ✅ Good: Common prefix shared
app.get('/api/v1/users', handler1)
app.get('/api/v1/posts', handler2)
app.get('/api/v1/comments', handler3)
// Only one 'api' and one 'v1' node created

// ❌ Less optimal: No shared prefixes
app.get('/users', handler1)
app.get('/posts', handler2)
app.get('/comments', handler3)
// Three separate root-level nodes

Source Code Reference

The TrieRouter implementation can be found at:

Router: src/router/trie-router/router.ts
Node: src/router/trie-router/node.ts

SmartRouter

Automatically selects the best router

RegExpRouter

High-performance router with some limitations

Routing Guide

Learn about choosing the right router

Route Parameters

Working with dynamic route parameters

Core

Built-in Middleware

Helpers

Routers

Adapters

Client

​Overview

​How It Works

​Algorithm Details

​Performance Characteristics

Static Routes

Dynamic Routes

Build Time

Memory

​When to Use

​Configuration

​Usage Examples

​Basic Routing

​Complex Parameter Patterns

​Optional Parameters

​Wildcard Routes

​Advanced Patterns

​How Matching Works

​Tree Traversal

​Pattern Priority

​Advanced Features

​Dynamic Route Registration

​Multi-Handler Resolution

​Parameter Validation

​Internal Architecture

​Node Structure

​Insert Process

​Search Process

​Comparison with Other Routers

​Performance Tips

​Performance Example

​Source Code Reference

​See Also