Trie Basics 10 XP Easy

Ctrl+Enter Run Ctrl+S Save

A Trie (pronounced "try") is a tree data structure used for storing strings efficiently. It's also called a prefix tree because it's amazing at prefix-based searches! 🌲

💡 Think of it like this: Imagine a dictionary where words with the same beginning share the same path. The words "cat", "car", and "card" all start with "ca", so they share the first two nodes!

#        root
#       / | \
#      c  d  ...
#      |
#      a
#     / \
#    t   r
#   (*)  |
#        d
#       (*)  ← (*) marks end of a word

Why Tries are powerful:

🔍 Search a word: O(length of word) — much faster than searching a list!
🔤 Autocomplete: Find all words with a given prefix (like Google search suggestions)
✅ Spell check: Quickly verify if a word exists
🎮 Word games: Boggle, Scrabble solvers use tries

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Complexity: Insert/Search/StartsWith all take O(length of word). Each node uses O(26) space in worst case (for lowercase English letters).

📋 Instructions

Build a trie from words ['apple','app','ape','bat','bar']. Count total nodes created (including root).

Insert each word. Count nodes by traversing the trie (BFS/DFS counting all TrieNodes).

⚠️ Try solving it yourself first — you'll learn more!

class TrieNode:
    def __init__(self):
        self.children = {}    # char → TrieNode
        self.is_end = False   # Does a word end here?

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 startsWith(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

🧪 Test Cases

Input

t.count_nodes()

Expected

10

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›