<filename>Implement Trie (Prefix Tree).py
class TrieNode:
    def __init__(self):
        self.next = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        n = self.root
        for w in word:
            if w not in n.next:
                n.next[w] = TrieNode()
            n = n.next[w]
        n.isWord = True

    def search(self, word):
        n = self.root
        for w in word:
            if w not in n.next:
                return False
            else:
                n = n.next[w]
        return n.isWord

    def startsWith(self, prefix):
        n = self.root
        for w in prefix:
            if w not in n.next:
                return False
            else:
                n = n.next[w]
        return True


if __name__ == '__main__':
    trie = Trie()
    trie.insert('apple')
    print(trie.search('apple')) # True
    print(trie.search('app')) # False
    print(trie.startsWith('app')) # True
    trie.insert('app') 
    print(trie.search('app')) # True
<filename>Implement Trie (Prefix Tree).py
class TrieNode:
    def __init__(self):
        self.next = {}
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        n = self.root
        for w in word:
            if w not in n.next:
                n.next[w] = TrieNode()
            n = n.next[w]
        n.isWord = True

    def search(self, word):
        n = self.root
        for w in word:
            if w not in n.next:
                return False
            else:
                n = n.next[w]
        return n.isWord

    def startsWith(self, prefix):
        n = self.root
        for w in prefix:
            if w not in n.next:
                return False
            else:
                n = n.next[w]
        return True


if __name__ == '__main__':
    trie = Trie()
    trie.insert('apple')
    print(trie.search('apple')) # True
    print(trie.search('app')) # False
    print(trie.startsWith('app')) # True
    trie.insert('app') 
    print(trie.search('app')) # True
# True # False # True # True