How to Solve Implement Trie (Prefix Tree)

Start by defining a TrieNode class with a hashmap for children and a flag for word completion. Insert words by traversing or creating nodes for each character. Search operations check the path character by character, and prefix queries verify the presence of a path without requiring full word matches, ensuring both time and space efficiency for up to 2000-character strings.

Problem Statement

Implement a Trie (Prefix Tree) that supports inserting words, searching for full words, and checking if any words start with a given prefix. The Trie should efficiently handle string storage and retrieval using a hash map for children nodes.

Design the Trie class with the following methods: insert(word) to store a string, search(word) to check if the word exists, and startsWith(prefix) to verify if any stored word begins with the given prefix. The Trie should support up to 3 * 10^4 operations, and words or prefixes contain only lowercase English letters up to length 2000.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["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"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

Constraints

• 1 <= word.length, prefix.length <= 2000
• word and prefix consist only of lowercase English letters.
• At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Solution Approach

Node Structure with Hash Map

Create a TrieNode class that stores child nodes in a hash map keyed by characters, and include a boolean flag indicating whether the node completes a valid word. This ensures O(1) child access per character.

Insert Method Traversal

Traverse the Trie character by character. For each character, check if it exists in the current node's hash map; if not, create a new node. Mark the last node as a completed word to differentiate full words from prefixes.

Search and Prefix Queries

To search, traverse nodes according to the characters and check the end-of-word flag for full words. For startsWith, traverse the prefix characters only and return true if the path exists, regardless of the end-of-word flag.

Complexity Analysis

Insertion, search, and prefix checks take O(L) time, where L is the length of the word or prefix, because each character requires a hash map lookup. Space is O(N * L) in the worst case, storing N words of length L, though shared prefixes reduce overall memory usage.

What Interviewers Usually Probe

• They may ask about handling large alphabets efficiently with hash maps.
• Expect questions on optimizing space with shared nodes or array-based children.
• They often probe edge cases like empty strings or maximum-length words.

Common Pitfalls or Variants

Common pitfalls

• Forgetting to mark the end-of-word flag, causing search to fail on full words.
• Using arrays instead of hash maps in languages with sparse character sets, wasting space.
• Confusing prefix checks with full word checks, returning incorrect results for startsWith.

Follow-up variants

• Implement a Trie that supports deletion of words while maintaining prefix correctness.
• Extend the Trie to store frequencies or counts for autocomplete ranking.
• Use a compressed Trie (Radix Tree) to reduce space for long strings with shared prefixes.

How GhostInterview Helps

• GhostInterview highlights the exact hash table plus string traversal pattern, saving time on setup and edge cases.
• It guides through node creation, marking end-of-word, and efficient child lookups, reducing common mistakes in Trie implementation.
• The solver flags pitfalls for prefix vs full word checks and offers quick test validation with examples like 'apple' and 'app'.

Topic Pages

• Hash Table
• String
• Design
• Trie

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main idea behind implementing a Trie (Prefix Tree)?

Use a tree structure where each node represents a character, storing children in a hash map and marking nodes that complete words.

How does the startsWith function differ from search in a Trie?

startsWith only checks that a path exists for the given prefix, while search also verifies the end-of-word flag to ensure a full word match.

Can I use arrays instead of hash maps for children in a Trie?

Yes, but arrays may waste space for sparse character sets; hash maps are more memory efficient for lowercase English letters.

What is the time complexity of insert, search, and startsWith?

All operations are O(L), where L is the length of the word or prefix, because each character requires a single lookup in the hash map.

How does this problem relate to the Hash Table plus String pattern?

Each Trie node uses a hash map (hash table) to store children characters, combining tree traversal with string processing for efficient queries.