Solution Review: Frequent Integers

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

// Definition of a trie node
class TrieNode
{
    public:
       	// children array store pointer to TrieNode of next 10 digits (0 to 9)
        TrieNode *children[10];
       	// A parameter to store the complete integer in the last node
        string num;
};

class Trie
{
    public:
        void addNum(TrieNode *root, int num)
        {
           	// point the current node 
           	// to the root
            TrieNode *curr = root;

            string numStr = to_string(num);
           	// iterate through the digits of the integers
            for (auto ch: numStr)
            {
                int index = ch - '0';

               	// create a new node for digit
               	// if not already present
                if (curr->children[index] == nullptr)
                {
                    curr->children[index] = new TrieNode();
                }

                curr = curr->children[index];
            }

           	// store the complete integer 
           	// in the last node 
            curr->num = numStr;
        }

    void getNum(TrieNode *curr, vector<int> &res, int k)
    {
       	// if bottom K integer are already in result
       	// return them
        if (curr == nullptr)
            return;

       	// if bottom K words are already in result
       	// return them
        if (res.size() == k)
            return;

       	// if last node is reached
       	// return the complete integers
        if (curr->num != ""
            and res.size() < k)
        {
            res.push_back(stoi(curr->num));
        }

       	// traverse the trie in pre order
       	// to get integers in lexicographical order
        for (int i = 0; i < 10; i++)
        {
            if (curr->children[i] == nullptr)
                continue;
            getNum(curr->children[i], res, k);
        }
    }
};

vector<int> leastFrequentNums(vector<int> &nums, int k)
{
    unordered_map<int, int> freqMap;

   	// iterate through the integers
   	// increment their frequency in map
    for (auto x: nums)
        freqMap[x]++;

    int n = freqMap.size();

   	// create a vector for trienodes 
   	// to store roots for tries storing 
   	// integers with different frequencies
    vector<TrieNode*> freqsTrieRoots;

   	// create root nodes 
    for (int i = 0; i <= n; i++)
    {
        TrieNode *newRootNode = new TrieNode();
        freqsTrieRoots.push_back(newRootNode);
    }

    Trie *trie = new Trie();
   	// based on the frequency
   	// add the integers to the associated trie
    for (auto x: freqMap)
    {
        trie->addNum(freqsTrieRoots[x.second], x.first);
    }

   	// initialize a vector for result
    vector<int> result;

   	// traverse the trie storing the
   	// lowest frequency integers first
    for (int i = 0; i < n; i++)
    {
        trie->getNum(freqsTrieRoots[i], result, k);
    }

    return result;
}