<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>

struct Tries 
{
    int val;
    Tries* link[10];
    bool end = false;


    Tries()
    {
        for(int i = 0; i <= 9 ; i++)
        {
            link[i] = (nullptr);
            
        }
    }

};
class Solution {
private:
    vector<int> res;
public:
    vector<int> lexicalOrder(int n) {
        Tries* root = new Tries();
      
        // put value in the tries
        for(int i = 1 ; i <= n ; i++)
        {
            Tries* ptr = root;
            string nStr = to_string(i);
            if(ptr == nullptr) return res;

            for(int j= 0; j < nStr.size(); j++)
            {
            
                int num = nStr[j] - '0';
                if(ptr && ptr -> link[num] == nullptr)
                {
                    ptr -> link[num] = new Tries();
                    
                } 
                ptr = ptr -> link[num];
            }
            ptr->val = i;
            ptr->end = true;
            
        }
        // traversal
        traversal(root);
        return res;
    }

     void traversal(Tries* ptr)
        {
            if (!ptr) return;
            if (ptr->end) res.push_back(ptr->val);
            
                for(int i = 0; i <= 9;i++)
                {
                    traversal(ptr -> link[i]);
                }
          

        }

};
26401