ReviseAlgo Logo

Trie (Prefix Tree)

Trie Fundamentals

Master Trie foundations: prefix trees, child node array allocations, prefix sharing properties, and complexity analysis.

Last Updated: August 2, 2026 • 15 min read

1. Introduction

What is a Trie?

A Trie (derived from the word retrieval, and pronounced like "try") or Prefix Tree is an ordered tree data structure used to store a dynamic set of strings, where the keys are usually strings.

Why is it Important?

Unlike balanced binary search trees or hash tables, the time complexity to search for a word of length L in a Trie is O(L), which is independent of the total number of words stored. Furthermore, Tries naturally group words sharing identical prefixes, saving space and enabling efficient prefix-matching checks.

Where is it Used?

  • Autocomplete & Autosuggest: Prompting potential search queries as the user types characters.
  • Spell Checkers: Validating if typed inputs exist inside dictionary prefix paths.

    • 2. Mental Model: The Forking Path Dictionary

    Imagine walking through a museum of words:

  • You enter the lobby (the root node). The lobby contains 26 doors labeled a through z.
  • If you want to find the word "cat", you go through door c.
  • In the next room, you see another set of 26 doors. You walk through door a.
  • In the third room, you walk through door t.
  • In that final room, you see a green flag labeled "Word Ends Here" (isEndOfWord = true).
  • If you were looking for "car", you would have followed the same doors c and a, but branched into door r instead of t. The prefix "ca" is shared!

    • 3. Core Node Representations

    A standard Trie node contains: 1. Children: An array of size 26 (for lowercase English letters) pointing to child Trie nodes. Alternatively, a HashMap can be used to support unicode/any characters. 2. isEndOfWord: A boolean flag indicating whether the node completes a valid word.

    4. Visualizing Prefix Sharing

    Below is a schematic of a Trie storing the words "cab", "car", and "cat":

    5. Real-World Examples

  • IP Router Prefixes: Storing network routing tables to classify IP subnets efficiently.
  • T9 Predictive Text: Old mobile phone keypads mapping digit key taps to prefix options.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers test structure optimization trade-offs:
  • "Compare a Trie vs a HashMap for storing a dictionary."
  • Trie advantages: Supports prefix matching (startsWith), yields words sorted alphabetically, and avoids hash collisions.
  • Trie disadvantages: High memory overhead because each node allocates a size-26 pointer array, many of which remain null.

    • Common Mistakes

    Warning: 1. Memory Bloat: Creating size-26 child arrays for sparse dictionaries consumes massive memory. For sparse character sets, use a HashMap backing instead of fixed arrays.
    > 2. Wrong Character Mapping: Accessing children[c - 'a'] without validating that character c is a valid lowercase letter, causing index out of bounds.

    7. Summary

  • Trie Node: Size-26 child node pointer array + isEndOfWord flag.
  • Prefix Sharing: Shared paths save memory for keys with identical starting strings.
  • Time Complexity: Insert/Search takes O(L) where L is word length (independent of dictionary size N).

    • 8. Quiz

    Question 1: What is the search time complexity to check if a word of length L exists in a Trie containing 1,000,000 words? Answer: O(L) time. We only step down L child nodes corresponding to the letters of the query, independent of the total words stored.
    Question 2: What is the space complexity of a Trie storing N words of average length L? Answer: O(N × L × 26) worst-case space (assuming no prefix sharing). In practice, prefix sharing reduces this footprint significantly.
    Question 3: If a Trie contains the word 'cart', does search('car') automatically return true? Answer: No. Even though the path c -> a -> r is traversed successfully, isEndOfWord at node r is false (since only t is tagged as a word ending), so search('car') returns false.
    Question 4: True or False: Tries are more space-efficient than HashMaps for storing small sets of completely random, non-overlapping words. Answer: False. With no common prefixes, no nodes are shared. Every character allocates a new node with a size-26 array of null pointers, causing massive memory bloat compared to a flat HashMap.
    Question 5: How does a Trie help implement predictive text autocomplete? Answer: We traverse the path of the typed prefix. From the prefix node, we run a DFS/BFS to collect all downstream child nodes that have isEndOfWord = true to yield suggestions.