Given an integer value $n$, write a function that returns all the numbers in the range $1$ to $n$ in lexicographical orderLexicographical order, also known as dictionary order or alphabetical order, is a way of ordering sequences (such as strings) based on the order of their elements. .

Constraints:

• $1 \leq n \leq 10^3$

Lexicographical order arranges words or sequences like in a dictionary. It compares items character by character, so “apple” comes before “banana” because 'a' is before 'b.' It's the same as alphabetical order but can apply to any sequence, not just words. Therefore, in the context of this problem, arranging the numbers in lexicographical order means that the numbers should be sorted as if they were strings, not as numerical values. For example, “10” comes before “2” because “1,” the first digit of “10”, is smaller than “2.”

To generate numbers in this order, we can think of the numbers as forming a tree, specifically a trie. The trie naturally organizes numbers in lexicographical order:

• The root is just an empty string “”.

• The first level after root has nodes against the numbers $1$, $2$, $3$, ..., $9$.

• Each of the nodes in the first level can have children. For example, $1$ can lead to $10$, $11$, $12$, ..., $19$. Similarly, $2$ can have children $20$, $21$, $22$, ..., $29$, and so on.

• The next level will have these children nodes having children. For example, $10$ can lead to $100$, $101$, $102$, ..., $109$, and so on.

Once we have planned to treat the numbers in a tree format, we traverse the nodes in this tree in the depth-first manner (go as deep as possible). Starting with $1$, we'll try to explore the smallest possible next number, which would be the $current ~~number$ $\times$$10$. However, when we can't go deeper because the next number would exceed $n$, backtrack and explore the next number at the same level. If that's also greater than $n$, go back to the previous level and explore the next valid number.

The algorithm works as follows:

• Create a TrieNode class that represents a node in the trie. It contains a dictionary, children, to store child nodes (digits) in the string form.

• Create a Trie class that represents the complete trie. It has a root node to store numbers, and the following methods:

  • insert: Adds the digits of each number one by one into the trie until $n$.

  • lexicographical_traversal: It perform DFS starting from the root, visiting children in sorted order (smallest digit first).

  • dfs: Recursively explores the trie, constructing numbers from the root. Backtracking happens if at any point:

    • The algorithm reaches the end of a branch, i.e., when a number cannot be extended further because there are no more child nodes.

• Insert all the numbers from $1$ to $n$ into the Trie using insert, and then call lexicographical_traversal that performs DFS to get numbers in lexicographical order.

Let’s look at the following illustration to better understand the solution.