Back
+20 XP
Concept

Async Web Framework: Trie-Based URL Path Routing

Linear regex matching slows to $O(N)$ as endpoints grow into hundreds of routes. Radix / Trie prefix trees segment URL paths into hierarchical nodes, resolving dynamic route parameters in $O(L)$ time proportional to path depth 🛣️.

python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.handler = None
        self.param_name = None

class Router:
    def __init__(self):
        self.root = TrieNode()

    def add(self, path, handler):
        curr = self.root
        for seg in path.strip("/").split("/"):
            if seg.startswith("{") and seg.endswith("}"):
                curr.param_name = seg[1:-1]
                curr = curr.children.setdefault(":", TrieNode())
            else:
                curr = curr.children.setdefault(seg, TrieNode())
        curr.handler = handler

    def match(self, path):
        curr = self.root
        params = {}
        for seg in path.strip("/").split("/"):
            if seg in curr.children:
                curr = curr.children[seg]
            elif ":" in curr.children:
                params[curr.param_name] = seg
                curr = curr.children[":"]
            else:
                return None, {}
        return curr.handler, params

router = Router()
router.add("/users/{id}", "user_view")
h, p = router.match("/users/42")
print(f"Handler: {h}, Params: {p} 🛣️")

# 114. Async Web Framework: Trie-Based URL Path Routing Linear regex matching slows to $O(N)$ as endpoints grow into hundreds of routes. Radix / Trie prefix trees segment URL paths into hierarchical nodes, resolving dynamic route parameters in $O(L)$ time proportional to path depth 🛣️. ```python class TrieNode: def __init__(self): self.children = {} self.handler = None self.param_name = None class Router: def __init__(self): self.root = TrieNode() def add(self, path, handler): curr = self.root for seg in path.strip("/").split("/"): if seg.startswith("{") and seg.endswith("}"): curr.param_name = seg[1:-1] curr = curr.children.setdefault(":", TrieNode()) else: curr = curr.children.setdefault(seg, TrieNode()) curr.handler = handler def match(self, path): curr = self.root params = {} for seg in path.strip("/").split("/"): if seg in curr.children: curr = curr.children[seg] elif ":" in curr.children: params[curr.param_name] = seg curr = curr.children[":"] else: return None, {} return curr.handler, params router = Router() router.add("/users/{id}", "user_view") h, p = router.match("/users/42") print(f"Handler: {h}, Params: {p} 🛣️") ``` Frameworks like Echo in Go, Fastify in Node, and modern Python engines use Radix trees to dispatch requests in microseconds even across thousands of registered endpoints 🚀! --- ### Question Why is Trie-based routing favored over linear regular expression checks in high-scale web routers? 🧠 - [ ] a. Lookup complexity is $O(L)$ based on path depth rather than $O(N)$ iterating through every registered regex pattern 🛣️ - [ ] b. Regex matching cannot extract string parameters - [ ] c. Trie trees consume zero CPU memory when compiled - [ ] d. Python's regex engine fails on paths containing slashes --- ### Challenge Build a Trie router. Register `'/api/{ver}'` mapping to `'api_handler'`. Match `'/api/v2'` and extract the `'ver'` parameter. Print it. 🎯 <details> <summary>Solution</summary> ```python class TrieNode: def __init__(self): self.children = {} self.handler = None self.param = None class Router: def __init__(self): self.root = TrieNode() def add(self, path, h): node = self.root for seg in path.strip('/').split('/'): if seg.startswith('{') and seg.endswith('}'): node.param = seg[1:-1] node = node.children.setdefault(':', TrieNode()) else: node = node.children.setdefault(seg, TrieNode()) node.handler = h def match(self, path): node = self.root params = {} for seg in path.strip('/').split('/'): if seg in node.children: node = node.children[seg] elif ':' in node.children: params[node.param] = seg node = node.children[':'] else: return None, {} return node.handler, params r = Router() r.add('/api/{ver}', 'api_handler') _, params = r.match('/api/v2') print(params['ver']) ``` </details>

Checkpoint

Why is Trie-based routing favored over linear regular expression checks in high-scale web routers? 🧠

Practice

Build a Trie router. Register `'/api/{ver}'` mapping to `'api_handler'`. Match `'/api/v2'` and extract the `'ver'` parameter. Print it. 🎯

Terminal
01
Tap code blocks below to assemble
Available Blocks