Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)

class TrieNode:
    children: map<char, TrieNode>   # up to 26 for lowercase a–z
    isEnd: bool                     # does a word END here?

def insert(self, word):
    node = self.root
    for c in word:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    node.isEnd = True

def search(self, word):
    node = self.root
    for c in word:
        if c not in node.children:
            return False
        node = node.children[c]
    return node.isEnd      # NOTE: not just True

def startsWith(self, prefix):
    node = self.root
    for c in prefix:
        if c not in node.children:
            return False
        node = node.children[c]
    return True            # path exists ⇒ prefix exists

def autocomplete(self, prefix):
    node = self.root
    for c in prefix:
        if c not in node.children: return []
        node = node.children[c]
    res = []
    def dfs(n, path):
        if n.isEnd: res.append(prefix + path)
        for c, child in n.children.items():
            dfs(child, path + c)
    dfs(node, "")
    return res