ReviseAlgo Logo

Strings

Trie (Prefix Tree) Introduction

Master Trie (Prefix Tree) fundamentals: TrieNode representation, insert, search, and startsWith operations in O(L) time.

Last Updated: August 2, 2026 • 25 min read

1. Introduction

What is a Trie (Prefix Tree)?

A Trie (pronounced "try", short for retrieval) is a tree-like data structure used to store a dynamic set of strings where nodes represent individual characters. Shared prefixes share the same parent node pathways in the tree.

Why is it Important?

While a HashSet checks if a full word exists in O(L) time (where L is word length), it cannot answer prefix queries like "find all words starting with 'app'" efficiently. A Trie performs both exact word lookups and prefix queries in O(L) time, completely independent of how many millions of words (N) are stored!

Where is it Used?

  • Autocomplete & Search Suggestions: Search bars (Google, Amazon) suggesting query completions.
  • Spell Checkers & T9 Predictive Text: Mobile keyboard dictionaries validating words as you type.

    • 2. Mental Model

    Imagine a Branching Tree Dictionary storing "cat", "car", and "do".

    Notice how "cat" and "car" share the exact same root path 'c' -> 'a'. You don't store "ca" twice! The character nodes are shared, saving memory and allowing instant prefix detection.

    3. Concept: TrieNode & Core Operations

    1. TrieNode Structure

    Each node contains:
  • children: Array of size 26 (for 'a'-'z') or a HashMap for arbitrary characters.
  • isEndOfWord: Boolean flag indicating if a valid word ends at this node.

    • 2. Implementation (insert, search, startsWith)

    4. Visuals

    Trie Node Hierarchy for ["cat", "car", "card", "dot"]

    5. Real-World Examples

  • IP Router Longest Prefix Matching: Forwarding internet packets to network routes matching the longest IP CIDR prefix.
  • T9 Phone Keypad Dictionary: Converting numeric sequences (228 \to cat) to word completions.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test Tries via prompts like: "Design Add and Search Words Data Structure", "Implement Trie", or "Word Search II (Grid DFS + Trie)".

    Common Mistakes

    Warning: 1. Forgetting isEndOfWord: Returning true when searching "app" inside a Trie containing only "apple". "app" is a prefix, but NOT a complete word unless isEndOfWord == true.
    > 2. High Memory Overhead: Using a size-26 TrieNode[] array for sparse dictionaries. If memory is tight, use a HashMap for children pointers.

    7. Summary

  • Operations: insert(), search(), and startsWith() all run in O(L) time (L = word length).
  • Prefix Advantage: Solves prefix queries in O(L) time independent of dictionary word count N.
  • Node Memory: Trade space for speed by storing shared character path nodes.

    • 8. Quiz

    Question 1: What is the time complexity of searching for a word of length L in a Trie containing 1,000,000 words? Answer: O(L) time. The lookup time depends ONLY on the word length L, not the number of words N in the dictionary.
    Question 2: What is the purpose of the isEndOfWord boolean flag in a TrieNode? Answer: To distinguish between a complete inserted word and a partial prefix (e.g., distinguishing "app" from the prefix pathway of "apple").
    Question 3: How does a Trie help solve the "Word Search II" (Grid Word Boggle) problem? Answer: By storing target words in a Trie, DFS grid traversal can immediately prune search paths if the grid path prefix doesn't exist in the Trie (startsWith() == false).
    Question 4: What is the space complexity of storing N words of length L in a Trie in the worst case? Answer: O(N × L × |\Sigma|), where |\Sigma| is the alphabet size (e.g., 26).
    Question 5: How does a HashMap child implementation compare to a fixed size-26 array child implementation? Answer: HashMap saves space for sparse nodes (nodes with few branches), but array lookup children[c - 'a'] is slightly faster on physical hardware due to direct indexing without hash collisions.