Trie for Prefix Search and Autocomplete

class TrieNode:
    __slots__ = ("children", "weight")

    def __init__(self) -> None:
        self.children: dict[str, TrieNode] = {}
        self.weight = 0


class Trie:
    def __init__(self) -> None:
        self.root = TrieNode()
        self.size = 0

    def insert(self, word: str, weight: int = 1) -> None:
        if not isinstance(word, str) or not word:
            raise ValueError("word must be a non-empty string")
        if weight < 0:
            raise ValueError("weight must be non-negative")
        node = self.root
        for char in word:
            child = node.children.get(char)
            if child is None:
                child = TrieNode()
                node.children[char] = child
            node = child
        if node.weight == 0:
            self.size += 1
        node.weight = weight

    def find(self, prefix: str) -> TrieNode | None:
        node: TrieNode | None = self.root
        for char in prefix:
            if node is None:
                return None
            node = node.children.get(char)
        return node

    def complete(self, prefix: str, limit: int = 5) -> list[tuple[str, int]]:
        if limit < 1:
            raise ValueError("limit must be at least 1")
        start = self.find(prefix)
        if start is None:
            return []
        found: list[tuple[str, int]] = []
        walk(start, prefix, found)
        found.sort(key=lambda item: (-item[1], item[0]))
        return found[:limit]


def walk(node: TrieNode, prefix: str, found: list[tuple[str, int]]) -> None:
    if node.weight > 0:
        found.append((prefix, node.weight))
    for char in sorted(node.children):
        walk(node.children[char], prefix + char, found)


def main() -> None:
    trie = Trie()
    for word, weight in [
        ("rust", 10),
        ("runner", 7),
        ("runtime", 5),
        ("ruby", 3),
        ("go", 9),
    ]:
        trie.insert(word, weight)
    print(trie.complete("ru", limit=3))
    print(trie.complete("xyz"))


if __name__ == "__main__":
    main()