TrieRouter

Tree-based router supporting all path patterns with consistent performance

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:

1. Each node represents a path segment
2. Static segments are stored as direct children
3. Dynamic parameters (:param) are stored as pattern nodes
4. Wildcards (*) are handled as special pattern nodes
5. 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
1. Split path into segments: '/api/users/:id' → ['api', 'users', ':id']
2. Traverse/create nodes for each segment
3. Identify patterns (static, :param, :param{regex}, *)
4. Store handler at final node with method and score
5. 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:

1. Group similar routes - Routes with common prefixes share tree nodes
2. Limit pattern complexity - Simple patterns match faster than complex RegExp
3. Avoid excessive wildcards - Each wildcard adds branches to explore
4. 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

See Also

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