Trie Data Structure — Prefix Tree for Students

A trie stores characters edge-by-edge from the root. Shared prefixes become shared paths, which makes prefix search and autocomplete-style queries natural.

Try this in Python

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

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


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

    def insert(self, word: str) -> None:
        n = self.root
        for ch in word:
            n = n.children.setdefault(ch, TrieNode())
        n.end = True

    def search(self, word: str) -> bool:
        n = self.root
        for ch in word:
            if ch not in n.children:
                return False
            n = n.children[ch]
        return n.end

    def starts_with(self, prefix: str) -> bool:
        n = self.root
        for ch in prefix:
            if ch not in n.children:
                return False
            n = n.children[ch]
        return True


t = Trie()
t.insert("apple")
print(t.search("apple"), t.starts_with("app"), t.search("ap"))

Key takeaways

• Each node is a map of next characters (or a fixed array for lowercase English).
• end marks a complete word—do not confuse with passing through a prefix.
• Depth equals string length for this simple trie.