[![Read Prev](/assets/imgs/prev.png)](/chapters/ch06.05-ex-implementing-a-trie.md)

## Ex. Implementing our Trie based `Router`

<!-- Build a Trie-based router with Node.js to handle URL patterns and their corresponding handler functions. Enhance the Trie data structure to support efficient routing of incoming HTTP requests. -->

This challenge is designed to push your boundaries and is considered to be more advanced than usual. It's completely okay if you don't crack it on your first attempt. The key is to persist, revisit your logic, and don't hesitate to iterate on your solutions.

Since we just built a Trie data structure that can efficiently insert and search words, we can further enhance its capabilities by extending it to implement a Trie-based router for matching URL patterns. This powerful application of `Trie` data structure is commonly utilized in web frameworks, where it plays a crucial role in efficiently routing incoming HTTP requests to their respective handler functions.

By building a `Trie`-based router, our framework can achieve optimal performance and scalability, ensuring that each request is efficiently directed to the appropriate handler for processing.

### Challenge 1: Implementing the `addRoute` method

#### Requirements

Create a new class, `TrieRouter`, similar to what we had earlier - `Trie`. Add a method, `addRoute`, that takes in a URL pattern (like `/home` or `/user/status/play`) as a first parameter and a handler function as second parameter. Then insert the URL pattern into the `TrieRouter`, associating the handler function with the last node of that pattern.

#### More details

1. **Class Definition**: Define a class named `TrieRouter`. This class should contain:

   - A root node, which is the starting point of the Trie.
   - A method called `addRoute`.

2. **Route Node**: Define a class named `RouteNode` which will represent all the nodes.

   1. `RouteNode` should contain the handler function, which will be `null` or `undefined` for all nodes except the end nodes of each URL pattern.

   2. `RouteNode` should also contain a `Map` to store its children nodes, where the key will be the URL segment eg "home" or "user", and the value will be another `RouteNode`

3. **Root Node**: The root node is an empty node of the type `RouteNode`, that serves as the starting point for inserting new URL patterns into the Trie. Initialize it in the constructor of `TrieRouter`.

4. **Method - `addRoute`**: This method takes in two parameters:

   - `path`: A string representing the URL pattern to add to the Trie. The URL pattern will be segmented by forward slashes `/`.

   - `handler`: A function that should be called when the URL pattern is matched.

   - Remove the trailing slash `/` from the `path` if it exists.

   - The method should insert the `path` into the `TrieRouter`, associating the `handler` function with the last node of that pattern.

5. **Trailing forward-slashes**: You should treat routes that end with a forward slash `/` the same as those that don't, so that `/home/` and `/home` point to the same handler.

6. **Repeated forward-slashes**: You should remove all the repeated `/` in the path.

   1. `/user//hello////` should resolve as `/user/hello`

   2. `/user//////////` should resolve as `/user`

7. **Reject URLs** that contain any kind of white space. For example `/   user/ node  /` should throw an error.

8. **Reject URLs** that do not start with `/`

   1. If someone uses `trieRouter.addRoute("hi/something")`, your code should throw an error.

Once implemented, we should be able to do something like this:

```js
const trieRouter = new TrieRouter();

function ref() {}

trieRouter.addRoute("/home/", ref);
trieRouter.addRoute("/  user/  status/play", function inline() {});

// /home -> valid
// /user/status/play -> valid
// /user/status -> invalid
// /user -> invalid
// /home/ -> valid
// /user/status/play/ -> invalid
```

You don't need to worry about making HTTP requests just yet. A correctly implemented `TrieRouter` should look like this after adding both the routes mentioned above -

```bash
                (Root)
                  |
      -----------------------
      |           |          |
    "home"      "user"     (other segments)
      |           |
function ref   "status"
                  |
                  |
               "play"
                  |
         function inline
```

Go ahead and implement your version of the `TrieRouter`, `RouteNode` and `addRoute`. Here's a starting boilerplate for the challenge. You may proceed without using the boilerplate code if you're comfortable.

You may then share your code to help others or to receive feedback in the [Github discussions](https://github.com/ishtms/learn-nodejs-hard-way/discussions) section. I'll try to review all the code submissions and provide feedback if required.

```js
class TrieRouter {
  constructor() {
    this.root = new RouteNode();
  }

  addRoute(path, handler) {
    /* Add route code goes here */
  }
}

class RouteNode {
  constructor() {
    /** Define handler and children map **/
  }
}
```

#### Hints

1. Remember that a Trie is a tree-like structure where each node represents a piece/segment of a URL. Understanding the hierarchy can simplify the process.

2. Before diving into implementing all the conditions like removing trailing slashes or spaces, make sure your Trie works with the simplest case, such as adding a single route.

3. Consider breaking the URL path into segments using `split("/")` and loop through the segments to traverse the Trie.

4. Keep in mind that the handler function is associated with the end node of the URL pattern. Make sure you place the handler only at the right node.

5. Use the `Map` in each node to store its children. When adding a new route, check if a node for a segment exists; if it does, traverse to it. Otherwise, create a new node.

6. To deal with trailing slashes, and repeated slashes, you could write utility functions that normalize the path before processing it.
7. You should throw an error if the path contains any whitespace.

#### Solution

Kudos to those who successfully implemented the `addRoute` function in the `TrieRouter` class. You've just completed the first difficult exercise in this book, showcasing not only your coding abilities but also your problem-solving skills.

For those who found this challenge particularly challenging, don't get discouraged. The complexities you faced are what deepen your understanding and enhance your coding skills. Consider revisiting this exercise after looking at the solution or scraping and starting again from scratch.

```js
class RouteNode {
  constructor() {
    this.children = new Map();
    this.handler = null;
  }
}

class TrieRouter {
  constructor() {
    this.root = new RouteNode();
  }

  addRoute(path, handler) {
    if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
    if (typeof handler !== "function") throw new Error("Handler should be a function");

    let currentNode = this.root;
    let routeParts = path.split("/").filter(Boolean);

    for (let idx = 0; idx < routeParts.length; idx++) {
      const segment = routeParts[idx].toLowerCase();
      if (segment.includes(" ")) throw new Error("Malformed path parameter");

      let childNode = currentNode.children.get(segment);
      if (!childNode) {
        childNode = new RouteNode();
        currentNode.children.set(segment, childNode);
      }

      currentNode = childNode;
    }
    currentNode.handler = handler;
  }
}

const trieRouter = new TrieRouter();

function ref() {}

trieRouter.addRoute("/home/", ref);
trieRouter.addRoute("/user/status/play", function inline() {});

trieRouter.printTree();
```

Let's visualize our tree. I've included a new `printTree` method inside the `TrieRouter` class prints all the nodes of our `TrieRouter` recursively:

```js
class TrieRouter {
  ...

  printTree(node = this.root, indentation = 0) {
    const indent = "-".repeat(indentation);

    node.children.forEach((childNode, segment) => {
      console.log(`${indent}${segment}`);
      this.printTree(childNode, indentation + 1);
    });
  }

  ...
}
```

To check our output, let's execute our file:

```js
const trieRouter = new TrieRouter();

function ref() {}

trieRouter.addRoute("/home/", ref);
trieRouter.addRoute("/user/status/play", function inline() {});
trieRouter.printTree();
```

Output:

```bash
$node trie_router.js

## OUTPUT
-home
-user
--status
---play
```

Looks perfect. Let's go through the code and understand what's going on.

#### Explanation

```js
class RouteNode {
  constructor() {
    // Create a Map to store children nodes
    this.children = new Map();

    // Initialize the handler to null
    this.handler = null;
  }
}
```

In the `RouteNode` class, each node is initialized with a `handler` set to `null`. This handler will hold a reference to the function we want to execute when a route matching the URL pattern is requested. Alongside the handler, we created a `children` Map. This Map will contain references to the next nodes in the Trie, allowing us to navigate through the Trie using URL segments as keys.

```js
class TrieRouter {
  constructor() {
    // Create a root node upon TrieRouter instantiation
    this.root = new RouteNode();
  }
}
```

The `TrieRouter` class acts as a manager for the Trie data structure. When an instance of this class is created, a `root` node is initialized. This root node acts as the entry point for any operation that needs to traverse the Trie, essentially representing the root of the Trie structure.

```js
addRoute(path, handler) {
    // Validate input types
    if (typeof path !== "string" || path[0] !== "/") throw new Error("Malformed path provided.");
    if (typeof handler !== "function") throw new Error("Handler should be a function");
}
```

The `addRoute` method is responsible for adding URL patterns and their corresponding handlers to the Trie. The method starts by validating the inputs, ensuring that `path` is a string that starts with a slash and `handler` is a function. If either of these conditions isn't met, an error is thrown.

```js
addRoute(path, handler) {
    ...
    // Split the path into segments and filter out empty segments
    let routeParts = path.split("/").filter(Boolean);
}
```

The next part of the `addRoute` method preprocesses the path. The path is split into its segments (parts between slashes), and any empty segments are filtered out.

```js
addRoute(path, handler) {
    ...
    // Start at the root node of the Trie
    let currentNode = this.root;

    // Loop through all segments of the route
    for (let idx = 0; idx < routeParts.length; idx++) {
        const segment = routeParts[idx].toLowerCase();
        if (segment.includes(" ")) throw new Error("Malformed path parameter");

        // Attempt to find the next node in the Trie
        let childNode = currentNode.children.get(segment);
        ...
}
```

The `addRoute` method continues by setting `currentNode` to the `root` of the Trie. A `for` loop then iterates through each segment in the `routeParts` array. For each segment, the code checks if a child node with that segment as the key already exists in the `children` Map of the current node. If the segment contains spaces, an error is thrown.

We're also converting the segment to lowercase to ensure case-insensitivity in our router. This means that `/home` and `/Home` will be treated as the same route.

```js
addRoute(path, handler) {
    ...

    // If the next node doesn't exist, create it
    if (!childNode) {
        childNode = new RouteNode();
        currentNode.children.set(segment, childNode);
    }

    // Move to the next node for the next iteration
    currentNode = childNode;
}
```

If a child node for the current segment does not exist, a new `RouteNode` is instantiated, and it's added to the `children` Map of the current node with the segment as the key. The current node is then updated to this new node, ready for the next iteration or to end the loop.

```js
addRoute(path, handler) {
    ...
    // Assign the handler to the last node
    currentNode.handler = handler;
}
```

After the loop completes, the handler function is associated with the last node in the path.

That's it. We now have a working implementation of our router that supports adding routes. The next challenge involves finding a route and returning the handler associated with it.

### Challenge 2: Implementing the `findRoute` method

#### Requirements

You've successfully implemented the `addRoute` method to build our `Trie`-based router. Now, lets extend our `TrieRouter` class by adding another method, `findRoute`. This method should take a URL pattern (e.g., `/home` or `/user/status/play`) as its parameter. Search the `TrieRouter` and find the handler function associated with the last node that matches the pattern.

#### More details

1. **Method - `findRoute`**: Add a method to your `TrieRouter` class called `findRoute`.

- This method should take a single parameter, `path`, which is a string representing the URL pattern to find in the Trie.

- Return the handler function associated with the last node of the matching URL pattern.

- If the URL pattern is not found, return `null` or some indication that the route does not exist.

2. **Path Normalization**: We do not need to worry about path normalization. We are searching for a route, not adding one. So, we expect the client to make a request with a path identical to the one configured in the router. For checks like - Whether the path starts with `/`? We do't need to worry about these is because Node.js's HTTP server will provide the URL path in this format.

3. **Traversal**: Start from the root node and traverse the Trie based on the URL segments. Retrieve the handler function from the last node if the path exists.

4. **Route Matching**: The Trie should now allow for a partial match. For instance, if a handler is set for `/user/status`, a request for `/user/status/play` should return null if `/user/status/play` has not been set!

5. **Case Sensitivity**: Make sure to convert the url paths into lower-case before matching. So `/AbC` and `/abc` should result to the same handler.

Once implemented, we should be able to do something like this:

```js
const trieRouter = new TrieRouter();

function homeHandler() {}
function userHandler() {}

trieRouter.addRoute("/home", homeHandler);
trieRouter.addRoute("/user/status", userHandler);

console.log(trieRouter.findRoute("/home")); // Should return homeHandler
console.log(trieRouter.findRoute("/user/status")); // Should return userHandler
console.log(trieRouter.findRoute("/user/status/play")); // Should return null
```

Feel free to share your implementation or ask for feedback in the [Github discussions](https://github.com/ishtms/learn-nodejs-hard-way/discussions) section. I'll try to review all code submissions and provide feedback if required.

#### Starting Boilerplate

Feel free to use the starting boilerplate below. If you are comfortable, you may proceed without it.

```js
class TrieRouter {
  constructor() {
    this.root = new RouteNode();
  }

  addRoute(path, handler) {
    /* Your addRoute code */
  }

  findRoute(path) {
    /* Your findRoute code goes here */
  }
}
```

#### Hints

1. When traversing the Trie, you may find it beneficial to break down the URL pattern into segments just like you did while inserting the route.

2. Be careful about the return values. Ensure you return the handler function if a match is found and a suitable indicator (like `null`) if no match exists.

#### Solution

Here's the solution that I came up with:

```js
class Router {
    constructor() {
        this.root = new RouteNode();
    }

    addRoute(path, handler) {
        ...
        /** Nothing changed **/
    }



    findRoute(path) {
        let segments = path.split("/").filter(Boolean);
        let currentNode = this.root;

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

            let childNode = currentNode.children.get(segment);
            if (childNode) {
                currentNode = childNode;
            } else {
                return null;
            }
        }

        return currentNode.handler;
    }


    printTree(node = this.root, indentation = 0) {
       /** Nothing changed **/
    }
}

class RouteNode {
    /** same as before **/
}
```

#### Explanation

```js
    findRoute(path) {
       // Split the path into segments and filter out empty segments
       let segments = path.split("/").filter(Boolean);

       // Start at the root node of the Trie
       let currentNode = this.root;
       ...
    }
```

We've initialized two key variables. The `segments` variable stores the differet parts of the URL split by `/`. That is, if the path is `/home/users`, the segments array will contain `["home", "users"]`. The `currentNode` variable keeps track of our current position in the Trie and is initialized to the root node.

```js
findRoute(path) {
    ...

    // Traverse the Trie based on the URL segments
    for (let idx = 0; idx < segments.length; idx++) {
        // Retrieve the current URL segment
        let segment = segments[idx];

        // Retrieve the child node corresponding to the current URL segment
        let childNode = node.children.get(currPart);
    ...
}
```

We loop through each segment of the `segments` array. Within the loop, `segment` holds the current URL segment, and `childNode` is obtained from the `children` map of the current `node` based on this segment. This part is crucial because we're determining if a child node exists for the current URL segment in our Trie.

```js
findRoute(path) {
    ...
     // If the next node exists, update the current node
     if (childNode) {
        currentNode = childNode;
     } else {
    // If the next node doesn't exist, exit the function with null to indicate no matching route
        return null;
     }

     // Since we've reached the end of the URL, return the handler if found, otherwise `null`
     return currentNode.handler;
    ...
}
```

First, this portio of the code checks whether `childNode` exists. If it doesn't, the function immediately returns `null`. This means that the Trie doesn't contain a matching route for the given URL, and there's no need to continue searching.

This allows us to move deeper into the Trie as we iterate through each URL segment. After the loop, the method returns the `handler` that was found. If no handler is found during the Trie traversal, the return value will be `null`.

Let's test our code:

```js
const trieRouter = new TrieRouter();

function ref() {}
function refs() {}

trieRouter.addRoute("/home/", ref);
trieRouter.addRoute("/user/status/play", function inline() {});
trieRouter.addRoute("/home/id", refs);
// trieRouter.addRoute("/throw/   error", function throwError() {}) // Should not let the program to run.

console.log(trieRouter.findRoute("/home/"));
console.log(trieRouter.findRoute("/home"));
console.log(trieRouter.findRoute("/home/id/"));
console.log(trieRouter.findRoute("/home/id/1"));
console.log(trieRouter.findRoute("/user/status/play"));
console.log(trieRouter.findRoute("/user/status/play/"));
```

This outputs:

```bash
[Function: ref]
[Function: ref]
[Function: refs]
null
[Function: inline]
[Function: inline]
```

Everything seems to be working well. This is it for the `findRoute` method. This was much easier than our `addRoute` implementation, since we only cared about searching. Excellent, we've grasped the basics well! Now let's move on to the more advanced features in the next chapter, ie Implementing HTTP methods with our router.

[![Read Next](/assets/imgs/next.png)](/chapters/ch06.07-ex-adding-http-methods.md)
