#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>


class Trie
{
private:
    struct Node {
        int end_node_count = 0; 
        std::unordered_map<char, Node*> children;
    };

private:
    void remove_trie(Node* node) 
    {
        for (auto [_, child] : node->children) {
            remove_trie(child);
        }
        delete node;
    }


public:
    Trie() 
        : m_trie(new Node())
    { }

    void add(const std::string &key)
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                trie->children[c] = new Node();
            }
            trie = trie->children[c];
        }

        trie->end_node_count++;
    }

    bool find(const std::string &key)
    {
        auto trie = m_trie;

        for (auto c : key) {
            if (trie->children.find(c) == trie->children.end()) {
                return false;
            }
            trie = trie->children[c];
        }

        return trie->end_node_count;
    }

    std::string max_freq_word() 
    {
        std::string max_word;

        max_freq_word(m_trie, max_word);

        return max_word;
    }

    ~Trie() 
    {
        remove_trie(m_trie);
    }
private:
    void max_freq_word(Node *node, std::string &max_word)
    {
        static std::string word;
        static int word_count;

        if (word_count < node->end_node_count) {
            word_count = node->end_node_count;
            max_word = word;
        }

        for (auto [c, child] : node->children) {
            word.push_back(c);
            max_freq_word(child, max_word);
            word.pop_back();
        }
    }

private:
    Node *m_trie;
};

int main(void)
{
    std::vector<std::string> words = 
    { 
        "cod", 
        "coder", 
        "coding", 
        "coding", 
        "cod", 
        "cod", 
        "codecs" 
    };

    auto trie = new Trie();

    for (auto word : words) {
        trie->add(word);
    }

    std::cout << trie->max_freq_word() << std::endl;

    delete trie;
    
    return 0;
}