Design a Trie (Prefix Tree)

Design and implement a Trie (Prefix Tree) data structure that efficiently stores and retrieves strings.

What is the Trie Problem?

Design and implement a Trie (Prefix Tree) data structure that efficiently stores and retrieves strings. The Trie should support insert, search, startsWith, autocomplete, and delete operations.

In this problem, you’ll design a system that can store thousands of words and allow users to search for exact matches or find all words starting with a specific prefix.

Problem Overview

Design a data structure that supports fast string operations, specifically optimized for prefix-based searches and autocomplete functionality.

Core Requirements

Functional Requirements:

Insert: Add a word by creating character nodes and marking the end-of-word.
Exact Search: Return true only if the full path exists and the last node is marked as end-of-word.
Prefix Matching: Support startsWith(prefix) to check if any words share the prefix.
Autocomplete: Use DFS from the prefix node to return all matching words.
Deletion: Remove words by unmarking flags and pruning unnecessary nodes.
Counting: Count all words in the Trie that share a specific prefix.
Edge Handling: Gracefully handle empty Tries, non-existent words, and empty strings.
Memory Optimization: Efficiently share common prefixes among words.

Non-Functional Requirements:

Time Complexity: O(m) for insert, search, and startsWith (m = word length).
Efficiency: Use DFS for autocomplete with O(m + k) complexity (k = number of results).
Modularity: Separate roles for Trie, TrieNode, and TraversalStrategy.
Extensibility: Easy to swap traversal algorithms or character sets.
Clean Architecture: Well-defined responsibilities following the Single Responsibility Principle.

What’s Expected?

1. System Architecture

The Trie is a tree where each node represents a single character and marks whether it completes a word.

2. Key Classes to Design

classDiagram
    class Trie {
        -TrieNode root
        +insert(word)
        +search(word) bool
        +startsWith(prefix) bool
        +autocomplete(prefix) List~String~
    }
    
    class TrieNode {
        -Map~char, TrieNode~ children
        -boolean isEndOfWord
        +getChild(char)
        +addChild(char)
    }

    Trie *-- TrieNode
    TrieNode "1" o-- "many" TrieNode : children

System Flow

Autocomplete Flow (`prefix: "ca"`)

Key Design Challenges

1. Space vs. Time (Array vs. Map)

In a TrieNode, should you use a fixed array children[26] or a HashMap<Character, TrieNode>?

Solution: Use a HashMap. While an array is slightly faster, a HashMap is more memory-efficient for sparse trees and easily supports Unicode characters beyond just lowercase English letters.

2. Efficient Deletion

When you delete “apple,” you should remove the ‘e’ node. If ‘l’ has no other children, it should also be removed. This requires “backtracking” up the tree.

Solution: Use Recursion. In the delete method, after unmarking isEndOfWord, check if the node has any children. If it has no children AND isEndOfWord is false, return null to the parent to signal that this branch can be pruned.

3. Autocomplete Scaling

Performing a full DFS on every keystroke for a huge dictionary can be slow.

Solution: Use Caching. Store a list of “top 10 results” directly in each TrieNode. As you insert words, update the cache in all parent nodes along the path. This turns autocomplete into an $O(M)$ operation instead of $O(M + K)$.

What You’ll Learn

By solving this problem, you’ll master:

✅ Tree Traversal - Using DFS and iterative logic to navigate nodes.
✅ Recursive Data Structures - Modeling parent-child relationships.
✅ Space Optimization - Understanding prefix sharing and pruning.
✅ String Matching Algorithms - The foundation for search engines and spell-checkers.

View Complete Solution & Practice

Ready to see the full implementation? Open the interactive playground to access:

🎯 Step-by-step guidance through the 8-step LLD approach
📊 Interactive UML builder to visualize your design
💻 Complete Code Solutions in Python, Java, C++, TypeScript, JavaScript, C#
🤖 AI-powered review of your design and code

🚀 View Solution in Playground

After mastering the Trie, try these similar problems:

Search Index - Building a reverse index for documents.
JSON Parser - Parsing hierarchical string data.
File System - Another tree-based resource manager.