Trie insertion and search in Data Structures Theory - Mini Project: Build & Apply

Trie insertion and search

📖 Scenario: Imagine you want to build a simple system to store and find words quickly, like a mini dictionary. A Trie is a special tree structure that helps with this by storing words letter by letter.

🎯 Goal: You will create a basic Trie structure by adding words to it and then searching for words inside it. This will help you understand how Tries work for fast word lookup.

📋 What You'll Learn

Create a Trie node structure to hold children letters and a flag for word end

Add a list of words to the Trie using insertion

Search for a word in the Trie to check if it exists

Use clear variable names like root, children, is_end, word

💡 Why This Matters

🌍 Real World

Tries are used in autocomplete systems, spell checkers, and IP routing to quickly find words or prefixes.

💼 Career

Understanding Tries helps in software development roles involving search optimization, text processing, and data structure design.

1

Create the Trie node structure

Create a class called TrieNode with an __init__ method that initializes children as an empty dictionary and is_end as False.

Data Structures Theory

# Your code here

Hint

Think of children as a place to store next letters, and is_end to mark if a word finishes here.

2

Set up the Trie root and words list

Create a variable called root as a new TrieNode() instance. Also create a list called words with these exact words: 'cat', 'car', 'dog'.

Data Structures Theory

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

# Your code here

Hint

The root is the starting point of the Trie. The words list holds the words you want to add.

3

Insert words into the Trie

Write a function called insert_word(word) that inserts the given word into the Trie starting from root. Use a for loop to go through each letter. If the letter is not in current.children, add a new TrieNode(). Move current to the child node. After the loop, set current.is_end = True. Then, use a for loop to insert each word from the words list by calling insert_word(word).

Data Structures Theory

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

root = TrieNode()
words = ['cat', 'car', 'dog']

# Your code here

Hint

Each letter creates or moves to a child node. Mark the end of the word with is_end = True.

4

Search for a word in the Trie

Write a function called search_word(word) that searches for the given word in the Trie starting from root. Use a for loop to check each letter. If a letter is not found in current.children, return False. Move current to the child node. After the loop, return the value of current.is_end to confirm if the word exists.

Data Structures Theory

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

root = TrieNode()
words = ['cat', 'car', 'dog']

def insert_word(word):
    current = root
    for letter in word:
        if letter not in current.children:
            current.children[letter] = TrieNode()
        current = current.children[letter]
    current.is_end = True

for word in words:
    insert_word(word)

# Your code here

Hint

Check each letter step by step. If any letter is missing, the word is not in the Trie. Otherwise, check if the last letter marks the end of a word.

Practice

1. What is the main purpose of a Trie data structure in storing words?

easy

A. To store words letter by letter in a tree for fast prefix search

B. To store words as a single string in a list

C. To store words in random order for quick access

D. To store words using hash codes only

Solution

1. Step 1: Understand Trie structure

   A Trie stores words by breaking them into letters and linking them in a tree structure.

2. Step 2: Identify purpose

   This structure allows fast searching of words by prefixes, unlike storing whole words as strings or hashes.

3. Final Answer:

   To store words letter by letter in a tree for fast prefix search -> Option A

4. Quick Check:

   Trie = letter-by-letter tree [OK]

Hint: Trie stores words letter by letter for prefix search [OK]

Common Mistakes:

• Thinking Trie stores whole words as strings
• Confusing Trie with hash tables
• Assuming Trie stores words randomly

2. Which of the following correctly describes the insertion process in a Trie?

easy

A. Replace existing nodes with new letters

B. Add the whole word as a single node

C. Insert letters only if the word is not already present

D. Add nodes for each letter if missing and mark the last node as end of word

Solution

1. Step 1: Review insertion steps

   Insertion checks each letter; if a letter node is missing, it creates it.

2. Step 2: Mark end of word

   After all letters are inserted, the last node is marked to show the word ends there.

3. Final Answer:

   Add nodes for each letter if missing and mark the last node as end of word -> Option D

4. Quick Check:

   Insert = add letters + mark end [OK]

Hint: Insert letter nodes if missing, mark last as word end [OK]

Common Mistakes:

• Inserting whole word as one node
• Not marking the end of word
• Replacing existing nodes unnecessarily

3. Given a Trie with words: cat, car, and dog, what will be the result of searching for cap?

medium

A. True, because 'cap' is similar to 'car'

B. True, because 'ca' prefix exists

C. False, because 'p' node does not exist after 'ca'

D. Error, search cannot handle missing nodes

Solution

1. Step 1: Check prefix nodes

   The Trie has nodes for 'c' and 'a' from 'cat' and 'car'.

2. Step 2: Verify next letter node

   There is no 'p' node after 'a', so 'cap' is not found.

3. Final Answer:

   False, because 'p' node does not exist after 'ca' -> Option C

4. Quick Check:

   Missing letter node means word not found [OK]

Hint: Search fails if any letter node missing [OK]

Common Mistakes:

• Assuming prefix presence means full word found
• Confusing similar words as found
• Expecting errors instead of false

4. Identify the error in this Trie insertion pseudocode:

for letter in word:
  if letter in current_node:
    current_node = current_node[letter]
  else:
    current_node[letter] = {}
current_node['end'] = True

medium

A. The 'end' marker is set outside the loop, should be inside

B. The else block should update current_node after adding new node

C. The loop should iterate over indices, not letters

D. The code incorrectly uses a dictionary for nodes

Solution

1. Step 1: Analyze insertion logic

   When a new letter node is created, the code does not move current_node to this new node.

2. Step 2: Identify fix

   After adding a new node, current_node must be updated to that node to continue insertion correctly.

3. Final Answer:

   The else block should update current_node after adding new node -> Option B

4. Quick Check:

   Update current_node after adding new letter node [OK]

Hint: Move current_node after adding new node [OK]

Common Mistakes:

• Not updating current_node after insertion
• Setting 'end' marker inside loop incorrectly
• Confusing iteration over letters vs indices

5. You want to insert the words bat, bath, and baton into a Trie. How many nodes will the Trie have after all insertions?

hard

A. 9 nodes

B. 8 nodes

C. 7 nodes

D. 10 nodes

Solution

1. Step 1: Insert 'bat'

   Creates nodes: 'b', 'a', 't' -> 3 nodes (root is not counted as a node).

2. Step 2: Insert 'bath'

   'b', 'a', 't' exist; add 'h' -> 1 new node; total 4 nodes.

3. Step 3: Insert 'baton'

   'b', 'a', 't' exist; add 'o', 'n' -> 2 new nodes; total 6 nodes.

4. Step 4: Count 'end' markers as nodes

   Each word end is marked, adding 3 'end' markers as nodes; total nodes = 6 + 3 = 9 nodes.

5. Step 5: Confirm total nodes

   Nodes: b, a, t, h, o, n plus 3 'end' markers = 9 nodes.

6. Final Answer:

   9 nodes -> Option A

7. Quick Check:

   Letter nodes + end markers = 9 [OK]

Hint: Count letter nodes plus 'end' markers as nodes = 9 [OK]

Common Mistakes:

• Counting duplicate nodes multiple times
• Ignoring shared prefixes
• Miscounting letters in longer words
• Not counting 'end' markers as nodes