<p>Given an integer <code>n</code>, return all the numbers in the range <code>[1, n]</code> sorted in lexicographical order.</p>

<p>You must write an algorithm that runs in&nbsp;<code>O(n)</code>&nbsp;time and uses <code>O(1)</code> extra space.&nbsp;</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> [1,10,11,12,13,2,3,4,5,6,7,8,9]
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 2
<strong>Output:</strong> [1,2]
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 5 * 10<sup>4</sup></code></li>
</ul>

class Trie:
    def __init__(self):
        self.children = {}
        self.isEndOfNumber = False

    def insert(self, number):
        node = self
        for digit in str(number):
            if digit not in node.children:
                node.children[digit] = Trie()
            node = node.children[digit]
        node.isEndOfNumber = True

    def search(self, node, curr):
        if node is None:
            return []
        res = []
        if node.isEndOfNumber:
            res.append(int(curr))
        for digit in sorted(node.children.keys()):
            res.extend(self.search(node.children[digit], curr + digit))
        
        return res
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        t = Trie()
    
        # Insert numbers 1 to n into the trie
        for i in range(1, n + 1):
            t.insert(i)
    
        # Pre-order traversal of the trie to get lexicographical order
        return t.search(t, "")
"""
For O(N) solution follow DFS based solution, else we can convert 
each integer to string, and use python's sort to sort in lexicographical 
order.

Tree-like Structure:
Imagine numbers as forming a tree where each node has up to 10 children. 
The root level (depth 0) has nodes 1 through 9. Each node at depth k 
(where k ≥ 1) represents the current number x, and its children are 
10*x, 10*x+1, ..., 10*x+9.
"""
"""
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []
        def dfs(curr):
            res.append(curr) 
            for i in range(10): #Start with the smallest number at each level (i.e., 1, then 10, then 100, etc.).
                nextNum = curr * 10 + i 
                if nextNum > n: #if nextNum is out of bounds, then go back to previous level
                    break
                dfs(nextNum)

        for i in range(1, 10): #The root level (depth 0) has nodes 1 through 9
            if i <= n:
                dfs(i)
        return res
"""

"""
O(NlogN) solution where N is the number given
Lexicographical order compares the first character of the strings. 
If the first characters are the same, it moves to the next character.
Python's sort() method sorts strings based on lexicographical order.
But given that we cant solve this solution in O(NlogN) need O(N)
"""
"""
class Solution:
    def lexicalOrder(self, n: int) -> List[int]:
        res = []
        for i in range(1, n+1):
            res.append(str(i))
        res.sort()
        for i in range(len(res)):
            res[i] = int(res[i])
        return res
"""
28600