// a -> p -> p -> l -> e

class Node {
public:
    Node() {}
    Node(char c) : c_(c) {
        
    }
    void addChild(char c) {
        if (!hasChild(c)) {
            children.emplace(make_unique<Node>(Node(c)));
        }
    }

    bool hasChild(char c) const {
        for (const auto& child : children) {
            if (child->c_.value_or(' ') == c) {
                return true;
            }
        }
        return false;
    }
    Node* getChild(char c) {
        for (const auto& child : children) {
            if (child->c_.value_or(' ') == c) {
                return child.get();
            }
        }
        return nullptr;
    }

    set<unique_ptr<Node>> children;
private:
    optional<char> c_ = nullopt;
};

class Trie {
public:
    Trie() : root_(Node{}){
        
    }
    
    void insert(string word) {
        Node* current = &root_;

        for (int i = 0; i < word.size(); ++i) {
            const char c = word[i];
            if (!current->hasChild(c)) {
                current->addChild(c);
            }
            current = current->getChild(c);
        }
        words.emplace(word);
    }
    
    bool search(string word) {
        return words.contains(word);
    }
    
    bool startsWith(string prefix) {
        Node* current = &root_;
        for (int i = 0; i < prefix.size(); ++i) {
            const char c = prefix[i];
            if (!current->hasChild(c)) {
                return false;
            }
            current = current->getChild(c);
        }
        return true;
    }
private:
    Node root_;
    set<string> words;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */