Trie

The Trie data structure is one of the most powerful tools for solving string-related coding interview problems. It appears frequently in medium and hard LeetCode problems. While arrays and hash maps handle exact lookups well, Tries excel when prefixes matter.

If you’ve ever solved problems involving autocomplete, word dictionaries, or prefix matching, you’ve already encountered situations where a Trie is the natural solution.

Once you understand how Tries store characters hierarchically and how prefix traversal works, many string problems become significantly easier and more structured.

A real-world intuition

Imagine you are using Google Search and you start typing “car.”

After typing “c”, Google already knows to ignore every query that does not start with “c.” After typing “ca”, it narrows the possibilities even further. After typing “car”, it can suggest “car rental,” “car insurance,” or “car price.”

Instead of looking through a giant list of every possible word (a linear search), Google follows a specific path of characters. It follows the prefix you are building and only considers completions that extend that prefix.

That is exactly how a Trie works.

Each character moves you one level deeper in the tree. If the path exists, matching words exist. If the path does not exist, you immediately know that no word with that prefix is stored.

What is a Trie?

In simple words, a Trie is a tree used to store strings character by character, where:

• Each node represents one character.
• A path from the root to a node forms a prefix.
• Words that share common prefixes share the same path in the tree.
• A special marker (usually a boolean flag) indicates that a complete word ends at that node.

This end-of-word marker is essential because a prefix is not necessarily a valid word. For example, if “car” is inserted, the node for “r” is marked as the end of a word, but the node for “c” or “ca” is not.

Formally, a Trie is an ordered tree where:

• Edges represent characters.
• Each node stores children pointers.
• A boolean flag marks end of word.

Structure of a trie node

Each node in a trie is designed to represent a prefix and to help you move to the next character efficiently. A typical trie node contains the following components.

• Children mapping: This stores references to the next nodes keyed by character (for example, ‘a’ → next node). If a character does not exist in the mapping, it means no inserted word continues with that character from this prefix.
• End-of-word marker (is_end): This boolean indicates whether a complete word ends at this node. This marker is necessary because a prefix can exist without being a valid word. For example, “ca” can be a prefix of “cat” without “ca” being an inserted word.

Here is the common Python structure:

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

Core operations of a Trie

A trie is most useful when you can quickly add words and query them. The three core operations you should know for interviews are insert, search for a full word, and search for a prefix. All these operations run in time proportional to the word length because you process one character at a time.

Insert a word

Insertion walks from the root through each character in the word. If a required child node does not exist, you create it. At the end, you mark the final node as an end-of-word.

Let’s look at the Python implementation of insertion in a Trie.

class TrieNode:
    def __init__(self):
        self.children = {}   # Maps a character -> child TrieNode
        self.is_end = False  # True if a complete word ends at this node


class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root represents the empty prefix

    def insert(self, word: str) -> None:
        node = self.root  # Start from the root for every insertion

        # Walk through the word one character at a time
        for i, ch in enumerate(word):
            # If the path for this character does not exist, create it
            if ch not in node.children:
                node.children[ch] = TrieNode()
                print(f"Step {i+1}: '{ch}' not found. Creating a new node for '{ch}'.")
            else:
                # Otherwise, reuse the existing node (shared prefix)
                print(f"Step {i+1}: '{ch}' found. Reusing the existing node for '{ch}'.")

            # Move down to the child node for the next character
            node = node.children[ch]

        # Mark the final node so this prefix becomes a complete word
        node.is_end = True
        print(f"Done: Marked the end of the word '{word}' at the last node.\n")


# Example: insert words and observe how prefixes are shared
trie = Trie()
for w in ["cat", "car", "care"]:
    print(f"Inserting: {w}")
    trie.insert(w)

• Time complexity: O(L) per insertion, where L is the length of the word.
• Space complexity:
  • Per insertion: O(L) in the worst case (when no characters of the word exist in the Trie yet).
  • Overall space (complete Trie): O(N . L) worst case, where N is the number of words and L is the average length. This happens if no words share common prefixes (e.g., “abc”, “def”, “ghi”). In practice, the space is often much lower because of shared prefixes.

Now, let’s look at the following illustration for a better understanding of how insertion works in a Trie.

1 / 7

Search for a full word

Searching walks the same path as insertion. If a character edge is missing, the word is not present. If traversal succeeds, you still must check is_end to ensure the word fully exists and is not just a prefix.

Let’s look at the Python implementation of searching a complete word in a Trie.

class TrieNode:
    def __init__(self):
        self.children = {}   # Maps each character -> next TrieNode
        self.is_end = False  # True if a complete word ends at this node


class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root represents the empty prefix

    def insert(self, word: str) -> None:
        node = self.root  # Always start from the root
        for ch in word:
            # Create the path if this character does not exist yet
            if ch not in node.children:
                node.children[ch] = TrieNode()
            # Move to the child node for the next character
            node = node.children[ch]
        # Mark the last node to indicate the full word is stored
        node.is_end = True

    def search(self, word: str) -> bool:
        node = self.root  # Start from the root to search the word
        for ch in word:
            # If a character path is missing, the word is not in the trie
            if ch not in node.children:
                return False
            # Move to the next node
            node = node.children[ch]
        # The word exists only if we end at a node marked as end-of-word
        return node.is_end


# Driver code
trie = Trie()

# Insert words into the trie
for w in ["cat", "car", "care"]:
    trie.insert(w)

# Search queries and print results
queries = ["cat", "ca", "car", "care", "card", "dog"]
for q in queries:
    print(f"search('{q}') -> {trie.search(q)}")

• Time complexity: O(L), where L is the length of the word.
• Space complexity: O(1) additional space (not counting the trie itself).

Now, let’s look at the following illustration for a better understanding of how searching a complete word works in a Trie.

1 / 5

Check whether a prefix exists

Prefix search follows the same path as insertion. If a character edge is missing, then no stored word can have that prefix. If traversal succeeds for all characters in the prefix, then the prefix exists in the trie. Unlike full-word search, you do not check is_end because a prefix does not need to be a complete word.

Let’s look at the Python implementation of checking whether a prefix exists in a Trie.

class TrieNode:
    def __init__(self):
        self.children = {}   # Maps each character -> next TrieNode
        self.is_end = False  # True if a complete word ends at this node


class Trie:
    def __init__(self):
        self.root = TrieNode()  # Root represents the empty prefix

    def insert(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end = True

    def starts_with(self, prefix: str) -> bool:
        node = self.root  # Start from the root to match the prefix
        for ch in prefix:
            # If the path breaks, the prefix does not exist in the trie
            if ch not in node.children:
                return False
            # Move to the next node in the prefix path
            node = node.children[ch]
        # If we matched all characters, the prefix exists
        return True


# Driver code
trie = Trie()
for w in ["cat", "car", "care"]:
    trie.insert(w)

prefixes = ["c", "ca", "car", "care", "cap", "d"]
for p in prefixes:
    print(f"starts_with('{p}') -> {trie.starts_with(p)}")

• Time complexity: O(L), where L is the length of the prefix.
• Space complexity: O(1) additional space (not counting the trie itself).

Now, let’s look at the following illustration for a better understanding of how searching a prefix works in a Trie.

1 / 4

Trie vs. HashSet

A trie and a hash map can both search a full word in O(L) time, because hashing a string still requires reading all L characters to compute the hash. The difference shows up when you need prefix-based queries. A trie can answer “does any word start with this prefix?” in O(L) by walking the prefix once, while a hash map does not naturally support prefix search without checking many keys.

Tries usually use more memory because they store nodes and pointers for many characters. However, they become the better choice when you need features like autocomplete, prefix counting, or pruning in search problems. If you only need exact word existence checks, a hash set or hash map is often simpler and more space-efficient.

When to use Trie in coding problems

You should strongly consider a trie when a coding problem has any of the following signals.

• The prompt mentions prefixes, such as “starts with,” “prefix,” or “shortest root word.”
• The task resembles autocomplete or search suggestions.
• The input includes a dictionary of many words and many lookup queries.
• You need to search words with a wildcard character like ‘.’.
• You need to find many words on a grid while pruning impossible prefixes early.
• You want to share work across many strings that overlap heavily in their prefixes.
• The task asks for maximum XOR or best XOR partner, which often uses a bitwise trie.
• The constraints suggest that checking every word for every query would be too slow.

Common mistakes and edge cases

These are mistakes that frequently cause wrong answers or timeouts.

1. You should not forget the is_end marker, because a prefix is not necessarily a valid full word.
2. You should not continue DFS in grid problems when the current path is not a trie prefix, because that defeats the main pruning benefit.
3. You should not assume the alphabet is always lowercase English letters unless the problem statement guarantees it.
4. You should handle duplicates intentionally, either by storing counts or by using a set for results.
5. You should consider empty strings and single-character words, because these cases can break end-of-word logic.