Trie Insert Operation

To insert a word, traverse from root, creating nodes as needed:

def insert(word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
    node.isEndOfWord = true

Walk through inserting "cat" then "car":

$1.$ Insert "cat": create c, then a (child of c), then t (child of a), mark t as end

$2.$ Insert "car": c exists, a exists (reuse!), create r (child of a), mark r as end

The path c→a is shared. This prefix sharing is what makes tries space-efficient for dictionaries with common prefixes.

Time: $O(L)$ where $L$ is word length.