Trie Data Structure

🌳 The Magic Word Tree: Understanding Tries

Once Upon a Time in Dictionary Land…

Imagine you have a magical tree that can find any word in the blink of an eye. Not a regular tree with leaves and branches—but a word tree where each branch is a letter, and following the right path spells out words!

This magical tree is called a Trie (pronounced “try”—like when you try something new!).

🎯 What is a Trie?

Think of your phone’s keyboard when you start typing:

• You type “c” → it suggests: cat, car, cool
• You type “ca” → now it shows: cat, car, cake
• You type “cat” → it knows exactly: cat!

That’s a Trie at work!

The Tree Analogy

Picture a tree in a playground:

• The trunk is empty (the starting point)
• Each branch is one letter
• Following branches spells words
• A star ⭐ marks where a real word ends

        (root)
        /    \
       c      d
      /        \
     a          o
    / \          \
   t⭐  r⭐        g⭐

This little tree knows: cat, car, dog

🔤 Trie Fundamentals

The Building Blocks

Every Trie has these simple parts:

How Letters Connect

// Each node is like a small box
const node = {
  children: {},    // Links to next letters
  isEndOfWord: false  // Is this a complete word?
};

Simple Example:

To store “hi” and “hey”:

    (root)
       |
       h
       |
       i⭐ ← "hi" ends here
       |
       (also connects to)
       |
       e
       |
       y⭐ ← "hey" ends here

Wait, that’s not right! Let me fix it:

      (root)
         |
         h
        / \
       i⭐  e
            |
            y⭐

Now “hi” and “hey” share the letter “h”!

🛠️ Trie Operations

Operation 1: INSERT (Adding Words)

Story Time: Adding a word is like creating a path in a forest. If the path already exists, you just walk it. If not, you build new steps!

function insert(word) {
  let current = root;

  for (let letter of word) {
    // Path exists? Walk it!
    // No path? Build it!
    if (!current.children[letter]) {
      current.children[letter] = {
        children: {},
        isEndOfWord: false
      };
    }
    current = current.children[letter];
  }

  // Plant a flag at the end!
  current.isEndOfWord = true;
}

Let’s add “cat” step by step:

1. Start at root → no “c”? Create it!
2. At “c” → no “a”? Create it!
3. At “a” → no “t”? Create it!
4. At “t” → Mark as word end ⭐

Operation 2: SEARCH (Finding Words)

Story Time: Searching is like following a treasure map. Each letter is a clue!

function search(word) {
  let current = root;

  for (let letter of word) {
    // Can't find next step?
    if (!current.children[letter]) {
      return false; // Word not here!
    }
    current = current.children[letter];
  }

  // Did we land on a real word?
  return current.isEndOfWord;
}

Searching for “cat”:

Step 1: root → "c" ✓ (exists!)
Step 2: "c" → "a" ✓ (exists!)
Step 3: "a" → "t" ✓ (exists!)
Step 4: Is "t" marked as end? ⭐ YES!

Result: FOUND! 🎉

Searching for “cab”:

Step 1: root → "c" ✓
Step 2: "c" → "a" ✓
Step 3: "a" → "b" ✗ (doesn't exist!)

Result: NOT FOUND 😅

Operation 3: DELETE (Removing Words)

Story Time: Deleting is careful work—like removing decorations without breaking the tree!

Rules for Deleting:

1. Remove the end-marker first
2. Remove letters only if no other word uses them
3. Never break paths to other words!

function delete(word) {
  deleteHelper(root, word, 0);
}

function deleteHelper(node, word, index) {
  // Reached the end?
  if (index === word.length) {
    node.isEndOfWord = false;
    return isEmpty(node);
  }

  let letter = word[index];
  let child = node.children[letter];

  // Should we remove this branch?
  if (deleteHelper(child, word, index + 1)) {
    delete node.children[letter];
    return !node.isEndOfWord && isEmpty(node);
  }

  return false;
}

🔮 Autocomplete with Tries

This is where Tries become MAGICAL!

How Your Phone Predicts Words

When you type “app”, your phone uses a Trie to:

1. Find the prefix → Navigate to “a” → “p” → “p”
2. Collect all words below that point
3. Show suggestions → apple, application, append

function autocomplete(prefix) {
  let current = root;
  let suggestions = [];

  // Step 1: Navigate to prefix end
  for (let letter of prefix) {
    if (!current.children[letter]) {
      return []; // Prefix doesn't exist!
    }
    current = current.children[letter];
  }

  // Step 2: Collect all words from here
  collectWords(current, prefix, suggestions);

  return suggestions;
}

function collectWords(node, currentWord, results) {
  // Found a complete word?
  if (node.isEndOfWord) {
    results.push(currentWord);
  }

  // Explore all children
  for (let letter in node.children) {
    collectWords(
      node.children[letter],
      currentWord + letter,
      results
    );
  }
}

Visual Example

Trie contains: app, apple, application, apt

User types: "app"

      (root)
         |
         a
         |
         p
         |
         p ⭐ ← We're here!
        / \
       l   [other branches...]
       |
       e ⭐
       |
       ...

Suggestions: ["app", "apple", "application"]

🔍 Word Search in Trie

The startsWith Magic

Sometimes you just want to know: “Does ANY word start with these letters?”

function startsWith(prefix) {
  let current = root;

  for (let letter of prefix) {
    if (!current.children[letter]) {
      return false;
    }
    current = current.children[letter];
  }

  // We reached the end of prefix!
  // (Doesn't matter if it's a complete word)
  return true;
}

Difference from Search:

🎮 Real-World Trie Powers

Where Tries Shine

graph TD
    A["Trie Uses"] --> B["📱 Autocomplete"]
    A --> C["🔤 Spell Check"]
    A --> D["🌐 IP Routing"]
    A --> E["🎮 Word Games"]
    B --> B1["Phone keyboards"]
    B --> B2["Search engines"]
    C --> C1["Red squiggly lines"]
    D --> D1["Network routing"]
    E --> E1["Wordle helper"]

Why Tries are Fast

The Secret: Trie speed depends on word length, not how many words exist!

🏆 Complete Trie Implementation

Here’s everything together:

class TrieNode {
  constructor() {
    this.children = {};
    this.isEndOfWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  // Add a word
  insert(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        node.children[char] = new TrieNode();
      }
      node = node.children[char];
    }
    node.isEndOfWord = true;
  }

  // Find exact word
  search(word) {
    let node = this.root;
    for (let char of word) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return node.isEndOfWord;
  }

  // Check if prefix exists
  startsWith(prefix) {
    let node = this.root;
    for (let char of prefix) {
      if (!node.children[char]) {
        return false;
      }
      node = node.children[char];
    }
    return true;
  }

  // Get all words with prefix
  autocomplete(prefix) {
    let node = this.root;
    let results = [];

    for (let char of prefix) {
      if (!node.children[char]) {
        return results;
      }
      node = node.children[char];
    }

    this.collectAll(node, prefix, results);
    return results;
  }

  collectAll(node, prefix, results) {
    if (node.isEndOfWord) {
      results.push(prefix);
    }
    for (let char in node.children) {
      this.collectAll(
        node.children[char],
        prefix + char,
        results
      );
    }
  }
}

💡 Key Takeaways

1. Trie = Tree for Strings

   • Each path from root to end-marker is a word

2. Super Fast Prefix Search

   • Find all words starting with “pro” instantly!

3. Memory Trade-off

   • Uses more memory, but blazing fast lookups

4. Perfect For:

   • Autocomplete ✨
   • Spell checkers ✨
   • Word games ✨
   • Search suggestions ✨

🚀 You’re Now a Trie Expert!

You’ve learned how Tries:

• Store words as connected letters
• Insert new words letter by letter
• Search in just O(word length) time
• Power autocomplete features
• Make prefix searching instant

Next time your phone suggests words, you’ll know the magic behind it! 🎉

Remember: A Trie is just a tree of letters where paths spell words. Simple as that!