LeetEye LeetEye
Medium Trie ~5 min

Implement Trie (Prefix Tree)

tries implement-trie-prefix-tree

Problem

A trie (pronounced as "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.

Examples

Example 1
Input: ["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
Output: [null, null, true, false, true, null, true]
Key Insight

Each node represents a character. A path from root spells a prefix. Mark nodes where words end.

Trie: tree where each path = prefix. Insert creates path and marks end. Search verifies path AND end marker. StartsWith just verifies path exists.

How to Approach This Problem

Pattern Recognition: When you see keywords like implement trie (prefix tree) tries, think Trie.

Step-by-Step Reasoning

1 Each trie node can have up to:
Answer: 26 children (for lowercase letters)
For lowercase English, each node can branch to any of 26 characters.
2 A trie node represents:
Answer: A single character in a prefix
Path from root to node = prefix. Each node = one more character added.
3 Why do we need an "is_end" or "is_word" flag?
Answer: To distinguish complete words from prefixes
"app" might be a prefix of "apple". We need to know if "app" itself was inserted as a complete word.
4 To insert "cat", we:
Answer: Create nodes for 'c', 'a', 't' along a path, mark 't' as end
Walk/create path c->a->t, mark the final node as a word end.
5 The difference between search and startsWith:
Answer: search checks is_end, startsWith doesn't
search needs exact match (complete word). startsWith just needs the path to exist.
6 Insert and search are:
Answer: O(m) where m is word length
We traverse one node per character. Independent of total words stored.

Solution

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

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
    
    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def startsWith(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Complexity Analysis

Time O(m) per operation
Space O(total chars)

Master This Pattern

Build intuition with interactive MCQs. Practice Trie problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye