Trie Data Structure

# CHAPTER 16

Trie Data Structure #

1. Introduction #

2. Learning Objectives #

• Understand the multi-child node architecture of a Trie.

• Map how strings share Prefix overlapping geometry.

• Execute $O(L)$ Time Complexity for ultra-fast word searching.

• Conceptualize real-world Autocomplete and Spell-Check algorithms.

3. The Anatomy of a Trie #

The Node Structure:

1. 1. An array or Hash Map of pointers to children (e.g., children['a'] = Node).

1. 2. A boolean flag: isEndOfWord. (This is critical to know if a path forms a complete valid word, or just the middle of a longer word).

Visualizing the Geometry: Let's insert the words: CAT, CAR, BAT.

          (Root)
          /    \
        'c'    'b'
        /        \
      'a'        'a'
      /  \         \
    't'* 'r'*      't'*

*Note: The * indicates isEndOfWord = True.* Notice that "CAT" and "CAR" share the exact same C -> A pathway! The tree does not duplicate the prefix. It simply branches at the third letter.

4. Inserting into a Trie #

1. 1. Start at Root. Does 'C' exist? Yes. Move to 'C'.

1. 2. Does 'A' exist under 'C'? Yes. Move to 'A'.

1. 3. Does 'P' exist under 'A'? No!

1. 4. Create a new Node for 'P' and attach it.

1. 5. Set the isEndOfWord flag to True on the 'P' node.

5. Searching in a Trie #

6. Application: Autocomplete Algorithm #

1. 1. The user types "CA".

1. 2. The algorithm traverses down to the 'A' node.

1. 3. From that specific 'A' node, it launches an aggressive DFS Traversal (Chapter 6) down all remaining nested branches.

1. 4. It discovers the isEndOfWord flags for 'T' (Cat), 'R' (Car), and 'P' (Cap), and instantly returns them as UI suggestions!

7. Complexity Analysis #

• Time Complexity (Search/Insert): $O(L)$, where $L$ is the Length of the word. Searching a 5-letter word takes 5 steps, even if the database has a Trillion words.

• Space Complexity: $O(N \times L)$. Tries consume massive amounts of RAM because they spawn thousands of node objects with empty 26-slot child arrays. (Optimized versions use Hash Maps instead of fixed arrays to save space).

8. Python Code Implementation #

class TrieNode:
    def __init__(self):
        self.children = {} # Using a Hash Map for memory optimization
        self.isEndOfWord = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            # If letter doesn't exist, create a new Node path
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char] # Move down
        node.isEndOfWord = True # Mark the final letter

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False # Path broken! Word doesn't exist.
            node = node.children[char]
        return node.isEndOfWord # Returns True if it's a complete word

9. Common Mistakes #

• Forgetting isEndOfWord: If you insert "CATCH" into a Trie, the nodes C-A-T exist. If you search for "CAT", the traversal will successfully find the 'T' node. But if you forget to check the boolean flag, your code will claim "CAT" was inserted, even though it wasn't! You MUST check isEndOfWord == True.

10. Exercises #

1. 1. Draw a visual Trie containing the words: APPLE, APPLY, API, and BAT. Mark the nodes that hold the boolean true flags.

1. 2. What is the Space Complexity drawback of using a fixed 26-element array for the children variable in every single node?

11. MCQs with Answers #

12. Interview Preparation #

• *System Design:* "How would you design the backend text storage for a mobile phone's 'Spell Checker' API?" *(Answer: A Trie Data Structure! Load a dictionary of 100,000 words. When the user types, trace the Trie. If the path hits a null edge before the word finishes, instantly draw a red squiggle under the text because the word is mathematically invalid!)*

13. Summary #

14. Next Chapter Recommendation #