Trie basics

A trie (also called a prefix tree, pronounced 'try') is a tree where each edge is one character. A word is stored as the path from the root down to a node, and that last node is marked 'end of word'. The root itself represents the empty string.

Words that start the same way share the same path. 'car', 'cart' and 'cat' all go through c then a, so the letters 'c' and 'a' are stored once. Each node keeps its children either in a hash map (char to node) or in a fixed array of 26 slots for lowercase English letters.

The key fact: insert, search and prefix check all take O(L) time, where L is the length of the string you are looking at. The number of words stored does not matter, which is what makes tries good for prefix questions that a hash set cannot answer.

1. 1Create a root node with an empty set of children and is_end = False.
2. 2Insert a word: start at the root. For each character, follow the child for that character, creating a new node if it does not exist. After the last character, set is_end = True on the node you are on.
3. 3Search for a word: walk the same way, but if a child is missing, return False immediately. If you reach the end, return the node's is_end flag, because the path may exist only as a prefix of a longer word.
4. 4Prefix check (starts_with): walk the prefix; if you never hit a missing child, some stored word starts with it, so return True. You do not look at is_end.
5. 5Delete (less common): walk to the word's last node and clear is_end; optionally remove nodes on the way back up that now have no children and are not the end of another word.

class TrieNode:
    def __init__(self):
        self.children = {}    # char -> TrieNode
        self.is_end = False   # True if a word ends at this node

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

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def _walk(self, s):
        node = self.root
        for ch in s:
            node = node.children.get(ch)
            if node is None:
                return None
        return node

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._walk(prefix) is not None

Each node holds a children dict and an is_end flag. insert creates missing nodes along the path, _walk follows an existing path or returns None, search needs the final node to be the end of a word, and starts_with only needs the path to exist. Every operation is O(L) for a string of length L.

Cost: Insert, search and starts_with are O(L) time for a string of length L. Space is O(total characters inserted) nodes in the worst case; with 26-slot arrays that is up to 26 pointers per node.