Trie Data Structure

🌳 The Magic Word Tree: Understanding Tries

Imagine you have a magical tree that can find any word super fast!

🎯 What is a Trie?

Think about your phone’s keyboard. When you type “H-E-L”, it shows “Hello”, “Help”, “Helicopter”. How does it guess so quickly?

Meet the Trie (pronounced “try”) — a special tree that stores words letter by letter!

The Library Analogy 📚

Imagine a library where books are sorted like this:

• All books starting with ‘A’ go to Aisle A
• Inside Aisle A, books with ‘AP’ go to shelf AP
• Inside shelf AP, books with ‘APP’ go to section APP
• And so on…

That’s exactly how a Trie works!

Finding "APPLE" in our word tree:
    (root)
      ↓
     [A] → found 'A'!
      ↓
     [P] → found 'P'!
      ↓
     [P] → found 'P'!
      ↓
     [L] → found 'L'!
      ↓
     [E] ✓ → found 'E'! Word complete!

🏗️ Trie Fundamentals

The Building Blocks

Every Trie has two simple parts:

1. Nodes (The Letter Boxes)

• Each node holds ONE letter
• Can connect to up to 26 children (a-z)
• Has a special flag: “Is this the end of a word?”

2. Root (The Starting Point)

• An empty node at the top
• Every word search begins here
• Like the entrance door of our library

What Makes Tries Special?

A Trie Node in Java

class TrieNode {
    TrieNode[] children;
    boolean isEndOfWord;

    TrieNode() {
        children = new TrieNode[26];
        isEndOfWord = false;
    }
}

What’s happening here?

• children[26] → slots for a-z
• isEndOfWord → “Does a word end here?”

⚙️ Trie Operations

Let’s learn the three magic spells to control our word tree!

🌱 Operation 1: INSERT (Planting Words)

The Story: You’re planting letters one by one, creating a path from root to the last letter.

void insert(String word) {
    TrieNode current = root;

    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (current.children[index] == null) {
            current.children[index] = new TrieNode();
        }
        current = current.children[index];
    }
    current.isEndOfWord = true;
}

Step by Step — Inserting “CAT”:

Start at root (empty)
    ↓
C: No 'C' child? Create one! Move to C.
    ↓
A: No 'A' child? Create one! Move to A.
    ↓
T: No 'T' child? Create one! Move to T.
    ↓
Mark T as "End of Word" ✓

🔍 Operation 2: SEARCH (Finding Words)

The Story: Walk down the tree letter by letter. If you reach the end AND the “end of word” flag is true, you found it!

boolean search(String word) {
    TrieNode current = root;

    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (current.children[index] == null) {
            return false;
        }
        current = current.children[index];
    }
    return current.isEndOfWord;
}

Example — Searching for “CAR”:

Start at root
    ↓
C: Found! Move to C node.
    ↓
A: Found! Move to A node.
    ↓
R: NOT found! Return false ❌

🔮 Operation 3: STARTS WITH (Prefix Check)

The Story: Same as search, but we don’t care if it’s a complete word. Just check if the path exists!

boolean startsWith(String prefix) {
    TrieNode current = root;

    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (current.children[index] == null) {
            return false;
        }
        current = current.children[index];
    }
    return true; // Path exists!
}

🔮 Autocomplete with Tries

This is where Tries become MAGICAL! ✨

How Your Phone Predicts Words

When you type “APP”, your phone:

1. Walks to the ‘A’ → ‘P’ → ‘P’ node
2. Explores ALL paths below
3. Collects every complete word
4. Shows you: “Apple”, “Apply”, “App”, “Application”

The Autocomplete Algorithm

List<String> autocomplete(String prefix) {
    List<String> results = new ArrayList<>();
    TrieNode current = root;

    // Step 1: Navigate to prefix
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (current.children[index] == null) {
            return results; // No matches
        }
        current = current.children[index];
    }

    // Step 2: Collect all words
    findAllWords(current, prefix, results);
    return results;
}

void findAllWords(TrieNode node,
                  String prefix,
                  List<String> results) {
    if (node.isEndOfWord) {
        results.add(prefix);
    }

    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            char c = (char) ('a' + i);
            findAllWords(
                node.children[i],
                prefix + c,
                results
            );
        }
    }
}

Visual Example

Words stored: cat, car, card, care, cart

Type "car":
         (root)
           ↓
          [c]
           ↓
          [a]
           ↓
    ╔══════[r]══════╗
    ║   ║   ║   ║   ║
   [d] [e] [t] ...
    ✓   ✓   ✓

Results: car, card, care, cart

🔎 Word Search in Trie

Beyond simple search, Tries can solve cool puzzles!

Problem: Search with Wildcards

What if someone types “c.t” where “.” means “any letter”?

We should find: “cat”, “cot”, “cut”!

The Solution

boolean searchWithWildcard(String word) {
    return searchHelper(word, 0, root);
}

boolean searchHelper(String word,
                     int index,
                     TrieNode node) {
    if (node == null) return false;

    if (index == word.length()) {
        return node.isEndOfWord;
    }

    char c = word.charAt(index);

    if (c == '.') {
        // Try ALL children
        for (int i = 0; i < 26; i++) {
            if (searchHelper(
                    word,
                    index + 1,
                    node.children[i])) {
                return true;
            }
        }
        return false;
    } else {
        // Normal character
        int idx = c - 'a';
        return searchHelper(
            word,
            index + 1,
            node.children[idx]
        );
    }
}

How “c.t” Search Works

Searching "c.t":

Step 1: c → Go to [C] node
Step 2: . → Try ALL children (a,o,u...)
Step 3: For each, check if 't' exists
         and is end of word

Found: cat ✓, cot ✓, cut ✓

🎮 Real-World Trie Magic

Where Tries Save the Day

The Complete Trie Class

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                node.children[i] = new TrieNode();
            }
            node = node.children[i];
        }
        node.isEndOfWord = true;
    }

    public boolean search(String word) {
        TrieNode node = findNode(word);
        return node != null && node.isEndOfWord;
    }

    public boolean startsWith(String prefix) {
        return findNode(prefix) != null;
    }

    private TrieNode findNode(String str) {
        TrieNode node = root;
        for (char c : str.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                return null;
            }
            node = node.children[i];
        }
        return node;
    }
}

🧠 Key Takeaways

The Trie Cheat Code

🌳 Trie = Tree for Words

📥 INSERT: Walk + Create nodes + Mark end
🔍 SEARCH: Walk + Check end flag
🔮 PREFIX: Walk + Return true if path exists
⚡ AUTOCOMPLETE: Walk to prefix + Collect all

Time Complexity Magic

Memory Trade-off

• Pro: Fast operations, prefix sharing
• Con: Each node stores 26 child pointers
• Tip: Use HashMap instead of array for sparse data

🎯 You Did It!

You’ve mastered the Trie data structure! 🎉

What you learned:

• ✅ What a Trie is (letter tree for words)
• ✅ Insert, Search, and Prefix operations
• ✅ Building autocomplete systems
• ✅ Advanced wildcard word search

Next time you use autocomplete on your phone, you’ll know the magic behind it — it’s a Trie! 🌳✨