Tries (Prefix Trees)

In the previous lesson, we studied AVL Trees and learned how self-balancing keeps search operations efficient.

Now we move to a very different type of tree — Tries, also called Prefix Trees.

Tries are designed not for numbers, but for strings, prefixes, and fast lookup.

Why Do We Need Tries?

Suppose you are building a search feature where users type:

“auto…”

As the user types each character, suggestions must appear instantly.

Using regular trees or hash tables would be inefficient for this task. This is where Tries shine.

What Is a Trie?

A Trie is a tree-like data structure where:

Each node represents a single character, and paths from the root represent words.

Unlike BSTs, Tries do not store complete keys at nodes. Instead, the structure itself represents the key.

Key Characteristics of Tries

Tries organize data character by character.

All words sharing a common prefix share the same path in the tree.

This makes prefix searching extremely fast and predictable.

Trie Structure Example

If we insert the words:

cat, car, can

All words share the prefix “ca”, so they share the same initial nodes.

Only the final branches differ.

End-of-Word Marker

Since one word may be a prefix of another, Trie nodes include an end-of-word flag.

This tells us whether a valid word ends at that node.

Example:

The word “car” ends earlier than “cart”.

Trie Node Representation

A Trie node typically contains:

• A dictionary or array of child nodes
• A boolean flag indicating end of word

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

Inserting a Word into a Trie

Insertion starts at the root.

For each character:

If the character does not exist, create a new node. Then move to that node.

After the last character, mark the end-of-word flag.

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

Searching for a Word

Search follows the same path character by character.

If a character is missing, the word does not exist.

At the end, the end-of-word flag determines validity.

def search(root, word):
    node = root
    for ch in word:
        if ch not in node.children:
            return False
        node = node.children[ch]
    return node.is_end

Prefix Search

One of the biggest advantages of Tries is prefix searching.

We only need to check whether the prefix path exists.

No need to search all words.

Time Complexity

For insertion, search, and prefix lookup, the time complexity is:

O(L), where L is the length of the word.

This is independent of the number of stored words.

Real-World Applications

Tries are heavily used in:

• Autocomplete systems
• Spell checkers
• Search engines
• IP routing
• Dictionary implementations

Trie vs Hash Table

Hash tables are excellent for exact lookups.

But they are weak at prefix searching.

Tries trade extra memory for powerful prefix capabilities.

Exercises

Quick Quiz

In the next lesson, we will explore Segment Trees, a powerful structure used for range queries and efficient updates.