LeetCode #208 Medium

Implement Trie (Prefix Tree)

Design a trie with insert(word), search(word), and startsWith(prefix).

triedesignstring

02

Intuition

💡

A trie stores words character by character down a tree: each node has up to 26 children, and words sharing a prefix share a path. Insert walks the word, creating missing children; search walks and checks an end-of-word flag; startsWith is the same walk without the flag. Every operation costs the word's length — independent of how many words are stored.

03

Approach

1

Node = children map + flag

Each node: dict char→child, plus end marking that some word terminates here. The flag is what separates search('app') from startsWith('app') when only 'apple' was inserted.

2

Insert = walk and create

From the root, follow each character's child, creating nodes as needed; set end on the last.

3

Search vs prefix

Both walk the same way and fail on a missing child. search additionally requires node.end at the last character.

04

Solution & live demo

python

▶1class Trie:
▶2    def __init__(self):
▶3        self.root = {}
▶4 
▶5    def insert(self, word):
▶6        node = self.root
▶7        for ch in word:
▶8            node = node.setdefault(ch, {})
▶9        node["$"] = True                 # end-of-word flag
▶10 
▶11    def _walk(self, s):
▶12        node = self.root
▶13        for ch in s:
▶14            if ch not in node: return None
▶15            node = node[ch]
▶16        return node
▶17 
▶18    def search(self, word):
▶19        node = self._walk(word)
▶20        return node is not None and "$" in node
▶21 
▶22    def startsWith(self, prefix):
▶23        return self._walk(prefix) is not None

05

Edge cases

search word that is only a prefix

Walk succeeds but end is False → False.

Insert a prefix of an existing word

No new nodes; just flag an interior node as end.

Duplicate insert

Idempotent — walk exists, flag already set.

06

Complexity

Time

O(L) per op

Space

O(total chars)

L = word length; shared prefixes stored once.