Big O Practice: Trie Insert Search

class Trie:
    def __init__(self):
        self.children = {}
        self.end = False

    def insert(self, word):
        node = self
        for c in word:
            if c not in node.children:
                node.children[c] = Trie()
            node = node.children[c]
        node.end = True

    def search(self, word):
        node = self
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.end

Variables

• k - length of the word being inserted or searched
• n - total characters across all inserted words

Explanation

Both insert and search walk one node per character - **O(k)** time per operation, where `k` is the length of the word. The trie as a whole holds one node per distinct prefix; total nodes are bounded by total characters across all inserted words, giving **O(n)** space overall.

More Big O practice problems · Today's daily problem