class Trie {
public:
    bool insert(string word) {
        if (!head) {
            head.reset(make_node(L'\0'));
        }
        
        bool foundPrefix = true;
        auto working = head.get();
        for (auto c : word) {
            const auto idx = c - 'a';       
            if (working->isLeaf) {
                // hit a prefix trying to insert the word
                return true;
            }
            
            if (!working->children[idx]) {
                // we are appending to the trie, so no prefix was found.
                working->children[idx].reset(make_node(c));  
                foundPrefix = false;
            }
            
            working = working->children[idx].get();
        }
        
        if (working) {
            working->isLeaf = true;
        }
        
        return foundPrefix;
    }
    
private:
    struct Node {
        char data;
        std::unique_ptr<Node> children[10];
        bool isLeaf;
    };
    
    Node* make_node(char d) {
        return new Node{ d, {}, false };
    }
    
    std::unique_ptr<Node> head{};
};

void noPrefix(vector<string> words) {
    Trie t;
    for (auto word : words) {
        if (t.insert(word))
        {
            printf("BAD SET\n");
            printf("%s\n", word.c_str());
            return;
        }
    }
    
    printf("GOOD SET\n");
}

# Node of a prefix tree
class Node:
    def __init__(self):
        self.children = {}
        self.EndOfWord = False

# Trie data structure
class Trie:
    def __init__(self):
        '''
        Initialize a prefix tree with a root node.
        '''
        self.root = Node()
    
    def insert(self, word: str) -> bool:
        '''
        Insert a word into the prefix tree. Return True if any existing word is a prefix of currently inserted word. Else, return False.
        '''
        current = self.root
        flag = False
        for c in word:
            if c not in current.children:
                current.children[c] = Node()
            current = current.children[c]
            if current.EndOfWord and not flag:
                flag = True
        current.EndOfWord = True 
        return flag
    
    def startswith(self, prefix:str) -> bool:
        '''
        Does the prefix tree contain entries starting with a specific prefix?
        '''
        current = self.root
        for c in prefix:
            if c not in current.children:
                return False
            current = current.children[c]
        return True
        
def noPrefix(words: list[str]) -> None:
    '''
    Say N = len(words) and L = max word length.
    Space complexity: O(NL)
    Time complexity: O(NL)
    '''
    # Write your code here
    trie = Trie()
    for word in words:
        # Check if word exists in trie. If not, add word to trie.
        if trie.startswith(word):
            print('BAD SET', word, sep='\n')
            return None
        # When inserting word into trie, determine if any pre-added word in trie is a prefix of the newly added word.
        bool_flag = trie.insert(word)
        if bool_flag:
            print('BAD SET', word, sep='\n')
            return None
    print('GOOD SET') 

//simple trie data struct
class PrefixTrie
{
    public:
  
    unordered_map<char, PrefixTrie*> children;

};

void noPrefix(vector<string> words) {
    PrefixTrie root;
    
    //track if we are creating a new branch
    bool onNewBranch = true;
    
    for(string w : words)
    {
        PrefixTrie *next = &root;
        
        //add the word to the trie
        //if we encounter a node with no children then that means
        //we have seen the word before and its a prefix so bad set
        //also, if we add the entire word and never got to a new branch
        //then its a prefix of a word already in the tree
        for(char c : w)
        {         
            
            //if the node has children then its not a word we have seen   
            if(next->children.empty() && !onNewBranch)
            {
                cout << "BAD SET\n" << w << "\n";
                return;
            }
            //if the character doesnt exist in the children
            //then we are making a new branch
            if(next->children.find(c) == next->children.end())
            {
                next->children[c] = new PrefixTrie();
                onNewBranch = true;
            }
            
            next = next->children[c];
        }
        //if we got here but didnt make our own branch then we 
        //are part of another word'd branch and therefor a prefix
        if(!onNewBranch)
        {
            cout << "BAD SET\n" << w << "\n";
            return;  
        }
        
        onNewBranch = false;
    }
    
    cout << "GOOD SET\n";
}