LeetCode 208 - Implement Trie (Prefix Tree)

The problem asks us to design and implement a Trie, also called a Prefix Tree. A Trie is a specialized tree structure for storing strings in a way that makes prefix-based operations very efficient.

leetcodemediumhash-tablestringdesigntrie

LeetCode Problem 208

Difficulty: 🟡 Medium
Topics: Hash Table, String, Design, Trie

Solution

Problem Understanding

The problem asks us to design and implement a Trie, also called a Prefix Tree. A Trie is a specialized tree structure for storing strings in a way that makes prefix-based operations very efficient.

We need to implement three operations:

  • insert(word) stores a word inside the Trie.
  • search(word) checks whether the exact word exists in the Trie.
  • startsWith(prefix) checks whether at least one inserted word begins with the given prefix.

The input consists of a sequence of method calls on the Trie object. Each operation modifies or queries the internal structure. The output for query operations is a boolean result indicating whether the requested word or prefix exists.

The key detail is that this structure is optimized for prefix matching. Unlike a normal hash set, where checking prefixes would require scanning many strings, a Trie organizes characters hierarchically so that shared prefixes reuse the same path in the tree.

The constraints are important:

  • Words and prefixes can be as long as 2000 characters.
  • There can be up to 3 * 10^4 operations.
  • All characters are lowercase English letters.

These constraints tell us that repeated string scanning must be efficient. A naive solution that repeatedly compares entire strings against all stored words could become very slow. Since only lowercase English letters are used, each node has at most 26 possible children, which makes Trie nodes compact and predictable.

Several edge cases are important:

  • A prefix may exist even if the full word does not.
  • A word can also be a prefix of another word.
  • Multiple inserted words may share long prefixes.
  • Searching for a word that was never inserted should return false even if part of it exists.
  • Re-inserting the same word should not break the structure.

For example, after inserting "apple":

  • startsWith("app") should return true
  • search("app") should return false

This distinction is the core idea behind Trie design.

Approaches

Brute Force Approach

A brute-force solution would store all inserted words inside a list or hash set.

For insert, we simply add the word to the collection.

For search, we check whether the exact word exists.

For startsWith, we iterate through every stored word and check whether any word begins with the given prefix.

This approach is straightforward and correct because every query directly examines the stored words. However, prefix queries become inefficient when many words are stored. If there are thousands of words, each startsWith call may require scanning all of them.

Since each word can be up to 2000 characters long, repeated prefix comparisons can become expensive.

Optimal Trie Approach

The key insight is that many words share common prefixes.

For example:

  • "apple"
  • "app"
  • "application"

all begin with "app".

Instead of storing these prefixes repeatedly, we can represent them once in a tree structure. Each node corresponds to a character, and paths from the root form words.

This allows us to process queries character by character:

  • Insert follows or creates nodes along the path.
  • Search verifies that every character path exists and that the final node marks a complete word.
  • Prefix checks only need to verify that the path exists.

This reduces the work from scanning all words to traversing only the characters in the query string.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * L) for prefix search O(N * L) Scans every stored word
Optimal Trie O(L) per operation O(N * L) Traverses only query characters

Here:

  • N is the number of stored words
  • L is the length of the word or prefix

Algorithm Walkthrough

Trie Structure

Each Trie node stores:

  • A mapping from characters to child nodes
  • A boolean flag indicating whether a complete word ends at this node

For example, inserting "app" and "apple" creates this structure:

root
 └── a
      └── p
           └── p (word ends here)
                └── l
                     └── e (word ends here)

Step-by-Step Algorithm

  1. Create a root node that represents the starting point of the Trie.

The root does not store a character itself. It only serves as the entry point for all words. 2. For insertion, begin traversal at the root.

For each character in the word:

  • Check whether a child node already exists.
  • If not, create a new node.
  • Move to the child node.

After processing all characters, mark the final node as a complete word. 3. For searching, again start from the root.

For each character:

  • If the character path does not exist, return false.
  • Otherwise move to the next node.

After all characters are processed, return whether the final node is marked as a complete word. 4. For prefix checking, traverse exactly like search.

The difference is that we do not require the final node to represent a complete word. We only care that the path exists. 5. Use a hash map for children storage.

A dictionary allows efficient lookup of child nodes by character. Since each lookup is approximately O(1), total traversal time becomes proportional only to the string length.

Why it works

The Trie maintains the invariant that every inserted word corresponds to a unique path from the root. Each node represents a prefix formed by the characters along that path.

Because insertion creates all required nodes, any valid prefix path will exist in the tree. Exact word existence is determined by the is_end marker, which distinguishes full words from mere prefixes.

Therefore:

  • If all characters of a prefix can be traversed, the prefix exists.
  • If traversal succeeds and the final node is marked as a word ending, the full word exists.

This guarantees correctness for all operations.

Python Solution

class TrieNode:
    def __init__(self):
        self.children: dict[str, "TrieNode"] = {}
        self.is_end = False

class Trie:

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

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

        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()

            current = current.children[char]

        current.is_end = True

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

        for char in word:
            if char not in current.children:
                return False

            current = current.children[char]

        return current.is_end

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

        for char in prefix:
            if char not in current.children:
                return False

            current = current.children[char]

        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

The implementation begins with a TrieNode class. Each node contains:

  • children, a dictionary mapping characters to child nodes
  • is_end, a boolean indicating whether a word terminates at this node

The Trie class stores a single root node.

The insert method walks through the characters of the word. If a character path does not exist, a new node is created. After processing the entire word, the final node is marked as a valid word ending.

The search method performs the same traversal. However, if any character is missing, the word cannot exist and the method returns False. After traversal finishes, the method checks is_end to ensure the word was fully inserted.

The startsWith method is simpler. It only verifies that the prefix path exists. It does not require the final node to mark a complete word.

Using dictionaries makes character lookup efficient and keeps the implementation clean.

Go Solution

package main

type TrieNode struct {
	children map[byte]*TrieNode
	isEnd    bool
}

type Trie struct {
	root *TrieNode
}

func Constructor() Trie {
	return Trie{
		root: &TrieNode{
			children: make(map[byte]*TrieNode),
		},
	}
}

func (this *Trie) Insert(word string) {
	current := this.root

	for i := 0; i < len(word); i++ {
		char := word[i]

		if _, exists := current.children[char]; !exists {
			current.children[char] = &TrieNode{
				children: make(map[byte]*TrieNode),
			}
		}

		current = current.children[char]
	}

	current.isEnd = true
}

func (this *Trie) Search(word string) bool {
	current := this.root

	for i := 0; i < len(word); i++ {
		char := word[i]

		if _, exists := current.children[char]; !exists {
			return false
		}

		current = current.children[char]
	}

	return current.isEnd
}

func (this *Trie) StartsWith(prefix string) bool {
	current := this.root

	for i := 0; i < len(prefix); i++ {
		char := prefix[i]

		if _, exists := current.children[char]; !exists {
			return false
		}

		current = current.children[char]
	}

	return true
}

/**
 * Your Trie object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */

The Go implementation follows the same logic as the Python version but uses explicit structs and pointers.

A few Go-specific details are worth noting:

  • The children field is implemented as map[byte]*TrieNode.
  • Since the input contains only lowercase English letters, indexing strings by byte is safe.
  • New child maps must be initialized using make.
  • Nodes are referenced using pointers to avoid unnecessary copying.

The overall traversal logic remains identical.

Worked Examples

Example 1

Operations:

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");
trie.search("app");
trie.startsWith("app");
trie.insert("app");
trie.search("app");

Step 1: Insert "apple"

Character Action Trie Path
a create node root → a
p create node a → p
p create node p → p
l create node p → l
e create node l → e

Mark node e as is_end = True.

Trie State

root
 └── a
      └── p
           └── p
                └── l
                     └── e*

* indicates a complete word ending.

Step 2: Search "apple"

Character Exists? Current Node
a Yes a
p Yes p
p Yes p
l Yes l
e Yes e

Final node has is_end = True.

Result:

True

Step 3: Search "app"

Character Exists? Current Node
a Yes a
p Yes p
p Yes p

Traversal succeeds, but final node has is_end = False.

Result:

False

Step 4: startsWith "app"

Character Exists?
a Yes
p Yes
p Yes

Traversal succeeds.

Result:

True

Step 5: Insert "app"

Traversal reuses existing nodes:

root → a → p → p

Now mark the final p node as is_end = True.

Updated Trie

root
 └── a
      └── p
           └── p*
                └── l
                     └── e*

Step 6: Search "app"

Traversal succeeds and final node now has is_end = True.

Result:

True

Complexity Analysis

Measure Complexity Explanation
Time O(L) Each operation processes each character once
Space O(N * L) Worst case stores all characters separately

Here:

  • L is the length of the word or prefix
  • N is the number of inserted words

Each Trie operation only traverses the characters in the input string. Since dictionary lookups are approximately constant time, the total runtime depends linearly on the string length.

The space complexity comes from storing Trie nodes. In the worst case, none of the words share prefixes, so every character requires a separate node.

Test Cases

# Provided example
trie = Trie()
trie.insert("apple")
assert trie.search("apple") is True       # exact word exists
assert trie.search("app") is False        # prefix is not yet a word
assert trie.startsWith("app") is True     # prefix exists
trie.insert("app")
assert trie.search("app") is True         # word now exists

# Single character word
trie = Trie()
trie.insert("a")
assert trie.search("a") is True           # single character search
assert trie.startsWith("a") is True       # single character prefix
assert trie.search("b") is False          # missing character

# Shared prefixes
trie = Trie()
trie.insert("cat")
trie.insert("car")
trie.insert("cart")
assert trie.search("cat") is True         # independent branch
assert trie.search("car") is True         # shared prefix word
assert trie.search("cart") is True        # longer extension
assert trie.startsWith("ca") is True      # common prefix
assert trie.startsWith("car") is True     # word as prefix

# Missing word with valid prefix
trie = Trie()
trie.insert("hello")
assert trie.search("hell") is False       # prefix but not word
assert trie.startsWith("hell") is True    # prefix exists

# Completely missing prefix
trie = Trie()
trie.insert("dog")
assert trie.startsWith("cat") is False    # unrelated prefix
assert trie.search("cat") is False        # unrelated word

# Repeated insertion
trie = Trie()
trie.insert("test")
trie.insert("test")
assert trie.search("test") is True        # duplicate insertion safe

# Long word
trie = Trie()
long_word = "a" * 2000
trie.insert(long_word)
assert trie.search(long_word) is True     # maximum length word
assert trie.startsWith("a" * 1999) is True  # long prefix
Test Why
Insert and search "apple" Validates basic functionality
Single character word Tests smallest valid input
Shared prefixes Verifies node reuse
Prefix but not full word Ensures is_end handling is correct
Missing prefix Confirms failed traversal handling
Duplicate insertion Ensures idempotent behavior
Maximum length word Tests constraint boundaries

Edge Cases

Prefix Exists but Word Does Not

This is the most important Trie edge case. After inserting "apple", the prefix "app" exists structurally in the Trie, but it should not count as a complete word unless explicitly inserted.

A buggy implementation might incorrectly return True for search("app") simply because the traversal succeeds. The is_end flag prevents this mistake by distinguishing complete words from intermediate prefixes.

Multiple Words Sharing Prefixes

Words such as "car", "cart", and "care" all share the prefix "car".

A naive tree implementation might accidentally overwrite nodes or fail to preserve existing paths. The Trie handles this correctly because insertion only creates missing nodes and reuses existing ones whenever possible.

This allows many words to coexist efficiently in the same structure.

Repeated Insertions

The problem does not forbid inserting the same word multiple times.

An incorrect implementation could create duplicate structures or corrupt state. In this solution, reinserting a word simply traverses the same path and sets is_end = True again. Since the flag is already true, the Trie remains valid and unchanged.