<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 Solution {
public:
    
    
    class trienode{
        
        public: 
        
       char data;
        trienode* children[10];
        bool isterminal;
        
        
        trienode(int c)
        {
            data=c;
            for(int i=0;i<10;i++)
            {
                children[i]=NULL;
            }
            
            isterminal=false;
            
        }
        
    };
    
    
    
    class trie{
        
        public:
        
        trienode* root;
        
        
        trie()
        {
            root = new trienode('-');
            
        }
        
        
        void insertutil(string word,trienode* root)
        {
            if(word.length()==0)
            {
                root->isterminal=true;
                return;
            }
            
            int index = word[0]-'0';
            trienode* child;
            
            if(root->children[index]!=NULL)
            {
                child=root->children[index];
            }else{
                
                child = new trienode(word[0]);
                root->children[index]=child;
                
            }
            
            insertutil(word.substr(1),child);
            
        }
        
        
        
        void insert(string word)
        {
            insertutil(word,root);
        }
        
        
        void getorderutil(trienode* root,string s,vector<int>& ans)
        {
            
            
            
            if(root->isterminal)
            {
                ans.push_back(stoi(s));
                
            }
            
            
            
            for(int i=0;i<10;i++)
            {
                if(root->children[i]!=NULL)
                {
                    s.push_back(root->children[i]->data);
                    getorderutil(root->children[i],s,ans);
                    s.pop_back();
                    
                    
                }
                
            }
            
            
        }
        
        
        
        void getorder(vector<int>& ans)
        {
            string s="";
            getorderutil(root,s,ans);
            
        }
        
        
        
    };
    
    
    
    
    vector<int> lexicalOrder(int n) {
        
        trie* t = new trie();
        
        for(int i=1;i<=n;i++)
        {
            t->insert(to_string(i));
        }
        
        vector<int> ans;
        
        t->getorder(ans);
        
        
      
        
        return ans;
        
        
    }
};
26665