juniorTrie

What is a Trie (Prefix Tree)?

Updated Apr 28, 2026

Short answer

A Trie, also called a Prefix Tree, is a tree-based data structure used to store and search strings efficiently by storing characters along paths from the root. Each node represents a character, and paths from the root represent prefixes or complete words. Tries are commonly used for autocomplete, dictionary lookups, spell checking, and prefix-based searching.

Deep explanation

A Trie stores a collection of strings by breaking each string into individual characters. Unlike a binary search tree or hash table, a Trie organizes data based on the characters themselves, allowing fast prefix operations.

For example, storing the words:

TEXT
cat
car
care
dog

would create a structure like:

TEXT
root
         /    \
        c      d
        |      |
        a      o
       / \     |
      t   r    g
          |
          e

Each path from the root represents a sequence of characters:

  • c -> a -> t represents "cat"
  • c -> a -> r represents "car"
  • c -> a -> r -> e represents "care"

The final node of a complete word is usually marked with a flag such as isWord = true to distinguish between a complete word and just a prefix.

For example, after inserting "app":

TEXT
root
 |
 a
 |
 p
 |
 p (end of word)

The node containing the second p represents both:

  • The complete word "app"
  • A prefix of words like "apple" and "application"

Main Operations

1. Insertion

To insert a word:

  1. Start from the root.
  2. Check whether a child node exists for each character.
  3. Create missing nodes.
  4. Mark the last node as the end of the word.

Example:

Python
def insert(word):
    node = root


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


        node = node.children[char]


    node.is_word = True

The time complexity is:

TEXT
O(L)

where L is the length of the inserted word.

2. Search

To search for a word, the Trie follows the character path from the root.

For example, searching for "car":

TEXT
root -> c -> a -> r

If every character exists and the final node is marked as a complete word, the search succeeds.

The time complexity is:

TEXT
O(L)

3. Prefix Search

One of the biggest advantages of a Trie is efficient prefix searching.

For example, finding all words beginning with "ca" only requires reaching:

TEXT
root -> c -> a

Then the Trie can explore all descendants of that node.

This makes Tries useful for features like:

  • Search autocomplete
  • Type-ahead suggestions
  • Word prediction

Trie Node Structure

A typical Trie node contains:

Python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False

Each node stores:

  • A collection of child nodes.
  • A marker indicating whether the node completes a valid word.

Advantages of Tries

  • Fast insertion and lookup based on word length.
  • Efficient prefix searching.
  • Avoids repeated string comparisons.
  • Naturally represents relationships between words with shared prefixes.

Disadvantages of Tries

  • Can use a lot of memory because every node stores references to children.
  • More complex to implement compared with hash tables.
  • Not always the best choice when only exact lookups are needed.

Trie vs Hash Table

A hash table provides average O(1) lookup for exact words:

TEXT
Find "apple" -> direct hash lookup

A Trie provides O(L) lookup:

TEXT
Find "apple" -> a -> p -> p -> l -> e

However, Tries have an important advantage: they can efficiently answer prefix-based questions, such as "find all words starting with app."

Real-world example

A search engine's autocomplete feature can use a Trie to suggest words as a user types.

Suppose the Trie contains:

TEXT
apple
application
app
banana

When a user types:

TEXT
app

the Trie quickly reaches the node:

TEXT
root -> a -> p -> p

Then it can return all words stored below that node:

TEXT
app
apple
application

A simple implementation:

Python
class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_word = False




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


    def insert(self, word):
        node = self.root


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


            node = node.children[char]


        node.is_word = True


    def starts_with(self, prefix):
        node = self.root


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


            node = node.children[char]


        return True

The starts_with operation only needs to check the characters in the prefix, making it efficient for autocomplete systems.

Common mistakes

  • * Thinking a Trie stores complete words inside every node instead of storing characters.
  • * Assuming Trie search complexity is `O(N)` because it contains `N` words.
  • * Forgetting to mark the end of a word and confusing prefixes with complete words.
  • * Using a Trie when only exact lookups are needed and a hash table would be simpler.
  • * Ignoring the memory cost caused by many Trie nodes and child references.
  • * Confusing a Trie with a binary tree because a Trie can have many children per node.

Follow-up questions

  • What is the time complexity of searching for a word in a Trie?
  • Why is a Trie useful for autocomplete systems?
  • How is a Trie different from a binary search tree?
  • What are the main disadvantages of using a Trie?
  • How can you optimize the memory usage of a Trie?

More Trie interview questions

View all →