DSAPrep
MediumTries

Implement Trie Prefix Tree

A trie (pronounced try) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.

void insert(String word) Inserts the string word into the trie.

boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.

boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1

Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]\n[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output: [null, null, true, false, true, null, true]
Explanation: Trie trie = new Trie(); trie.insert("apple"); trie.search("apple") returns true; trie.search("app") returns false since only "apple" was inserted; trie.startsWith("app") returns true; trie.insert("app"); trie.search("app") now returns true.

Constraints

  • 1 <= word.length, prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3 * 10^4 calls in total will be made to insert, search, and startsWith.
View original on LeetCode ↗

A trie stores strings character by character along root-to-node paths, so that words sharing a prefix also share the nodes for that prefix. Each node marks whether a complete word ends there, which is what separates “a string that was inserted” from “a string that just happens to be a prefix of something inserted.”

Brute Force: List of Words

Time insert O(L), search/startsWith O(n·L)Space O(n·L)

Just keep every inserted word in a list (or set). insert is trivial. search checks for an exact match; startsWith checks whether any stored word starts with the given prefix — both require scanning the whole collection in the worst case.

class Trie:
    def __init__(self):
        self.words = []


    def insert(self, word: str) -> None:
        self.words.append(word)


    def search(self, word: str) -> bool:
        return word in self.words


    def startsWith(self, prefix: str) -> bool:
        return any(w.startswith(prefix) for w in self.words)

Correct, but search on a plain list is O(n·L) (n words, each comparison up to length L), and startsWith is worse since it cannot stop early — every stored word must be checked. With up to 3·10^4 calls this is far too slow to be the intended solution; it exists here mainly to highlight what the trie buys us.

Trie with Character Nodes

OptimalTime O(L) per operationSpace O(total characters inserted)

Build an explicit tree: each node holds a map from character to child node, plus a flag for “a word ends here.” insert walks the word, creating any missing nodes along the way, then flags the final node. search/startsWith both walk the same way and just differ in what they check once the walk finishes: search requires the end-of-word flag, startsWith only requires the path to exist.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False


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


    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True


    def search(self, word: str) -> bool:
        node = self._find(word)
        return node is not None and node.is_word


    def startsWith(self, prefix: str) -> bool:
        return self._find(prefix) is not None


    def _find(self, s: str):
        node = self.root
        for ch in s:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

Tracing insert("cat"), insert("car"), then a few queries — car and cat share the c -> a prefix path, so inserting car only needs to create one new node (r):

•
1 / 7
comparingseenresultcurrentdiscarded

Start with an empty trie: just the root node, no children yet.

Complexity: every operation walks exactly one character per level, so each is O(L) where L is the length of the word or prefix — independent of how many words are stored. Space is bounded by the total number of distinct characters across all inserted prefixes, since shared prefixes only cost one set of nodes.