Code › algorithm-study

LeetCode 208 - Implement Trie (Prefix Tree)

Implementing a Trie with fixed 26-child nodes and an is_end marker

algorithmleetcodetrieprefix-treedata-structurepythonlearning

This Medium data-structure problem asks for a Trie that supports insertion, exact word lookup, and prefix lookup. Because the input is limited to lowercase English letters, I used a fixed 26-child array on each node and an is_end flag to mark complete words.

A Trie stores strings one character at a time. Unlike a set or hash table that treats the whole word as one key, a Trie lets words with the same prefix share the same path.

If I insert apple, the Trie creates a path from the root through a, p, p, l, and e. After that, app already has a path, but app has not been inserted as a full word. That means search should return false, while startsWith should return true.

insert("apple")
search("apple")    -> true
search("app")      -> false
startsWith("app")  -> true
insert("app")
search("app")      -> true

That distinction is why node existence is not enough for exact search. The Trie also has to remember whether a node was the final character of an inserted word.

Approach

I started by separating the node from the Trie itself. Each TrieNode owns a children array and an is_end flag.

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

The children array maps directly to the 26 lowercase letters. For a character c, the index is ord(c) - ord(‘a’). If the child at that position does not exist yet, insert creates a new TrieNode. If it already exists, the code reuses that node and keeps walking down the path.

Insertion starts at the root and processes the word one character at a time. After the last character, the current node is marked as the end of a complete word.

cur = self.root

for c in word:
    idx = ord(c) - ord('a')
    if not cur.children[idx]:
        cur.children[idx] = TrieNode()
    cur = cur.children[idx]

cur.is_end = True

search follows the same path-building logic without creating nodes. If a required child is missing, the word is not in the Trie and the function returns False immediately. If every character is found, search returns cur.is_end.

startsWith uses the same traversal, but its final condition is different. It only needs to know whether the prefix path exists, so after the loop it returns True without checking is_end.

The apple and app case makes the boundary concrete. After inserting only apple, the path a -> p -> p exists, so startsWith(“app”) is True. But that third p node has not been marked as a word ending yet, so search(“app”) is False. Inserting app later walks the existing path again and only changes that node’s is_end flag.

Complexity analysis

Let L be the length of the word, and let P be the length of the prefix.

  • insert time complexity: O(L)

    • The operation processes each character once. Index calculation and child access are constant-time operations because the alphabet size is fixed.

  • insert extra space complexity: O(L)

    • Existing prefix nodes are reused, but if none of the path exists yet, insertion can allocate one new node per character. Each node stores 26 child references and one end marker. Since 26 is fixed by the problem constraints, the number of newly allocated nodes is O(L).

  • search time complexity: O(L)

    • Exact lookup traverses the input word character by character.

  • search extra space complexity: O(1)

    • It only keeps the current node reference and an index.

  • startsWith time complexity: O(P)

    • Prefix lookup traverses the prefix once.

  • startsWith extra space complexity: O(1)

    • It does not allocate another data structure while checking the prefix.

For the full Trie after many insertions, storage is proportional to the number of nodes created by all inserted strings. If T is the total number of inserted characters, the worst-case node count is O(T). Each node carries 26 child slots, so the constant factor is noticeable, but the alphabet size is fixed and the usual asymptotic space bound is O(T).

Implementation code

class TrieNode:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False


class Trie:

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

    def insert(self, word: str) -> None:
        cur = self.root

        for c in word:
            idx = ord(c) - ord('a')
            if not cur.children[idx]:
                cur.children[idx] = TrieNode()
            cur = cur.children[idx]

        cur.is_end = True

    def search(self, word: str) -> bool:
        cur = self.root

        for c in word:
            idx = ord(c) - ord('a')
            if cur.children[idx]:
                cur = cur.children[idx]
            else:
                return False

        return cur.is_end

    def startsWith(self, prefix: str) -> bool:
        cur = self.root

        for c in prefix:
            idx = ord(c) - ord('a')
            if cur.children[idx]:
                cur = cur.children[idx]
            else:
                return False

        return True

Summary and reflection

The main decision in this problem is the shape of TrieNode. With a fixed lowercase alphabet, a 26-child array gives direct indexing for each character, and shared prefixes naturally reuse the same path. The is_end flag then separates a path that merely exists from a path that represents a complete inserted word.

search and startsWith look almost identical while traversing the Trie, but they answer different questions at the end. search asks whether the whole input was inserted as a word, so it must check is_end. startsWith only asks whether the path exists, so the traversal itself is enough. That final condition is small in code, but it defines the difference between exact lookup and prefix lookup.