The Word Tree.

How a trie thinks — four moves

1. The root is empty. Every path starts there; each step down consumes one character of a word.
2. Insert: walk & grow. For each letter, follow the child if it exists or create it. Mark the final node is_end = true.
3. Share prefixes for free. CAT and CAR both walk C→A, so that prefix exists once. Only the diverging letters add nodes.
4. Search vs startsWith. Both walk the letters. search also requires the end flag; startsWith only needs the path to exist.

The whole thing in code

class Trie:
    def __init__(self):
        self.kids = {}          # letter -> Trie node
        self.end = False

    def insert(self, word):
        node = self
        for ch in word:
            if ch not in node.kids:
                node.kids[ch] = Trie()   # grow
            node = node.kids[ch]
        node.end = True          # a word ends here

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

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

    def _walk(self, s):
        node = self
        for ch in s:
            if ch not in node.kids: return None
            node = node.kids[ch]
        return node