#include <iostream>
#include <vector>
#include <string>
#include <map>


class Trie
{
private:
    struct Node {
        bool end_node = false; 
        std::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 = true;
    }

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

    void get_words(std::vector<std::string> &words)
    {
        get_words(m_trie, words);
    }

    ~Trie() 
    {
        remove_trie(m_trie);
    }

private:
    void get_words(Node *node, std::vector<std::string> &words)
    {
        static std::string word;

        if (node->end_node) {
            words.push_back(word);
        }

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

private:
    Node *m_trie;
};

void trie_sort(std::vector<std::string> &words)
{
    auto trie = new Trie();

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

    words.resize(0);
    trie->get_words(words);
}

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

    trie_sort(words);

    for (auto word : words) {
        std::cout << word << std::endl;
    }
    
    return 0;
}