Trie Data Structure

The Magic Dictionary Tree: Understanding Tries

🌳 What is a Trie? A Story About a Library

Imagine you walk into a magical library. But this isn’t an ordinary library. Instead of books on shelves, every word you could ever want to find is stored in a giant tree.

Each branch of the tree represents a single letter. To find a word, you simply walk down the branches, one letter at a time.

This is a Trie (pronounced “try”) - a tree-like data structure that stores strings character by character.

🎯 Trie Fundamentals

The Simple Idea

Think of your phone’s contact list. When you type “M”, it shows all names starting with M. Type “Ma”, it narrows down to Maria, Mark, Maya. Type “Mar”, only Maria and Mark remain.

That’s exactly how a Trie works!

Each node in a Trie:

• Holds one character
• Points to children nodes (next possible letters)
• Has a flag saying “a word ends here”

The Building Blocks

graph TD
    ROOT["Root"] --> C["c"]
    ROOT --> D["d"]
    C --> A1["a"]
    A1 --> R1["r"]
    R1 --> END1["car - END"]
    A1 --> T1["t"]
    T1 --> END2["cat - END"]
    D --> O["o"]
    O --> G["g"]
    G --> END3["dog - END"]

    style END1 fill:#90EE90
    style END2 fill:#90EE90
    style END3 fill:#90EE90

What you see above:

• Empty root node at top
• Words “car”, “cat”, “dog” stored
• “car” and “cat” share “ca” (saves space!)

Python Trie Node

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

Two simple things:

• children: A dictionary holding next letters
• is_end: True if a word ends at this node

🔧 Trie Operations

Operation 1: Insert a Word

The Story: You’re adding a new book to the magic library. Walk down existing paths. Create new branches when needed.

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_end = True

Step by step for “cat”:

1. Start at root
2. ‘c’ not found → create ‘c’ node
3. Move to ‘c’ node
4. ‘a’ not found → create ‘a’ node
5. Move to ‘a’ node
6. ‘t’ not found → create ‘t’ node
7. Move to ‘t’ node
8. Mark as word end ✓

Operation 2: Search for a Word

The Story: Looking for a book? Follow the path letter by letter. If you reach the end AND find the “word ends here” flag - success!

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

Searching “cat”:

• Follow c → a → t
• Check: is_end = True? ✓
• Found it!

Searching “ca”:

• Follow c → a
• Check: is_end = True? ✗
• Not a complete word!

Operation 3: StartsWith (Prefix Search)

The Story: “Show me all books starting with ‘ca’!” You just need to find if the path exists - no need for the end flag.

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

🔮 Autocomplete with Tries

The Magic of Suggestions

When you type “pyt” on Google, it suggests:

• python
• python tutorial
• python download

How? A Trie storing millions of search terms!

Building Autocomplete

def autocomplete(self, prefix):
    results = []
    node = self.root

    # Step 1: Navigate to prefix end
    for char in prefix:
        if char not in node.children:
            return []
        node = node.children[char]

    # Step 2: Find all words from here
    self._find_words(node, prefix, results)
    return results

def _find_words(self, node, current, results):
    if node.is_end:
        results.append(current)
    for char, child in node.children.items():
        self._find_words(child, current + char, results)

Visual Example

graph TD
    ROOT["Root"] --> P["p"]
    P --> Y["y"]
    Y --> T["t"]
    T --> H["h"]
    H --> O["o"]
    O --> N["n"]
    N --> END1["python - END"]

    style T fill:#ff9900
    style H fill:#ffcc00
    style O fill:#ffcc00
    style N fill:#ffcc00
    style END1 fill:#90EE90

Type “pyt” → System finds ‘t’ node → Explores all paths below → Returns “python” and more!

🔍 Word Search in Trie

The Detective Game

Word search is like being a detective. You have a grid of letters. You need to find if specific words hide inside.

The Challenge

Given a 2D board:

[['o','a','a','n'],
 ['e','t','a','e'],
 ['i','h','k','r'],
 ['i','f','l','v']]

Find words: [“oath”, “eat”, “rain”]

The Trie Solution

Step 1: Put all target words in a Trie

Step 2: Start from each cell, explore all directions

Step 3: Use Trie to quickly eliminate bad paths

def find_words(board, words):
    # Build Trie from words
    trie = Trie()
    for word in words:
        trie.insert(word)

    found = []
    rows, cols = len(board), len(board[0])

    def explore(r, c, node, path):
        char = board[r][c]
        if char not in node.children:
            return

        child = node.children[char]
        new_path = path + char

        if child.is_end:
            found.append(new_path)
            child.is_end = False

        # Mark visited
        board[r][c] = '#'

        # Explore neighbors
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if board[nr][nc] != '#':
                    explore(nr, nc, child, new_path)

        # Restore cell
        board[r][c] = char

    # Start from every cell
    for r in range(rows):
        for c in range(cols):
            explore(r, c, trie.root, "")

    return found

Why Trie Wins Here

Without Trie: Check every word against every path = SLOW!

With Trie: Prune impossible paths early = FAST!

If no word starts with “xy”, stop immediately. Don’t waste time exploring further.

🎯 Complete Trie Implementation

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = 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_end = True

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

    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

⚡ Why Tries Are Amazing

n = number of words, m = word length, k = results

🌟 Real-World Trie Uses

1. Phone Contacts - Quick name lookup
2. Search Engines - Autocomplete suggestions
3. Spell Checkers - Finding similar words
4. IP Routing - Network address lookup
5. Word Games - Scrabble, Wordle helpers

🎉 You Did It!

You now understand:

• ✅ What a Trie is (a letter-by-letter tree)
• ✅ How to insert and search words
• ✅ How autocomplete works
• ✅ How to solve word search puzzles

The Trie is your new superpower for anything involving words and prefixes!