A Trie implementation in Python3.

trie.py

#! /usr/bin/env python3

from typing import Any, Dict

class Node:
    def __init__(self, value=None):
        self.value: Any = value
        self.children: Dict[str, Node] = {}

class Trie:
    def __init__(self):
        self.root = Node("root")

    def insert(self, key, value):
        dummy = self.root

        for character in key:
            if character not in dummy.children:
                dummy.children[character] = Node()

            dummy = dummy.children[character]

        dummy.value = value

    def retrieve(self, key):
        dummy = self.root

        for character in key:
            if character in dummy.children:
                dummy = dummy.children[character]
            else:
                raise KeyError(f"KeyError: {key} does not exist!")
        
        if dummy.value is None:
            raise KeyError(f"KeyError: {key} does not exist!")
        else:
            return dummy.value

if __name__ == "__main__":
    t = Trie()

    elements = [
        ("google", 100),
        ("gooogle", 1001),
        ("goooooooogle", 100002),
        ("gopher", 1000003),
        ("sayan", 42)
    ]

    for (k, v) in elements:
        t.insert(k, v)

    queries = ["sayan", "google", "gopher", "goog", "thiskeydoesnotexist"]

    for q in queries:
        try:
            val = t.retrieve(q)
            print(f"{q}: {val}")
        except KeyError as e:
            print(e)