Trie Insert Operation in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Trie after inserting words

What is the printed structure of the Trie after inserting the words "cat", "car", "dog" in order?

DSA Python

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

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 print_trie(self, node=None, word=''):
        if node is None:
            node = self.root
        if node.is_end:
            print(word)
        for char, child in node.children.items():
            self.print_trie(child, word + char)

trie = Trie()
words = ["cat", "car", "dog"]
for w in words:
    trie.insert(w)
trie.print_trie()

A

car
cat
dog

B

cat
car
dog

C

cat
dog
car

D

dog
car
cat

💡 Hint

The print_trie method traverses children in dictionary insertion order (Python 3.7+).

The Trie stores words by characters. The print_trie method recursively prints words when is_end is True. Children are iterated in insertion order (Python 3.7+). For 'cat' and 'car', the 't' child is inserted before the 'r' child under the 'ca' node, so 'cat' prints before 'car', followed by 'dog'. The correct output is: cat car dog

❓ Predict Output

intermediate

Trie node children count after insertions

After inserting the words "apple", "app", "ape" into an empty Trie, how many children does the root node have?

DSA Python

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

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

trie = Trie()
words = ["apple", "app", "ape"]
for w in words:
    trie.insert(w)

print(len(trie.root.children))

A 1

B 2

C 3

D 0

💡 Hint

All words start with the letter 'a'.

All inserted words start with 'a', so the root node has only one child for 'a'.

🔧 Debug

advanced

Identify the error in Trie insert method

What error will this code raise when inserting the word "bat" into the Trie?

DSA Python

class TrieNode:
    def __init__(self):
        self.children = []
        self.is_end = False

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

trie = Trie()
trie.insert("bat")

A No error, inserts successfully

B AttributeError: 'TrieNode' object has no attribute 'children'

C KeyError: 'b'

D TypeError: list indices must be integers or slices, not str

💡 Hint

Check the type of children and how it is accessed.

children is a list, but code tries to access children[char] where char is a string, causing TypeError.

❓ Predict Output

advanced

Trie structure after inserting overlapping words

After inserting "to", "tea", "ted", "ten" into an empty Trie, which words will be printed by this code?

DSA Python

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

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 print_words(self, node=None, prefix=''):
        if node is None:
            node = self.root
        if node.is_end:
            print(prefix)
        for char in sorted(node.children.keys()):
            self.print_words(node.children[char], prefix + char)

trie = Trie()
for w in ["to", "tea", "ted", "ten"]:
    trie.insert(w)
trie.print_words()

A

to
tea
ted
ten

B

ted
ten
to
tea

C

tea
ted
ten
to

D

ten
ted
tea
to

💡 Hint

Children are printed in sorted order of keys at each node.

The print_words method sorts children keys before recursion, so words print in lex order: 'tea', 'ted', 'ten', 'to'.

🧠 Conceptual

expert

Why use a Trie for prefix search?

Which of the following best explains why a Trie is efficient for prefix search compared to a list of strings?

A Trie stores words in a tree structure allowing prefix matching in O(k) time where k is prefix length, unlike list which requires checking each word.

B Trie sorts all words alphabetically, so binary search can be used for prefix matching.

C Trie compresses all words into a single string, making search faster than list scanning.

D Trie stores words in hash tables, so prefix search is O(1) time always.

💡 Hint

Think about how Trie nodes represent characters and how prefix search works.

Trie allows prefix search by traversing nodes for each prefix character in O(k) time. Lists require checking each word, which is slower.

Practice

1. What is the main purpose of the insert operation in a Trie data structure?

easy

A. To delete a word from the Trie

B. To add a new word character by character into the Trie

C. To search for a word in the Trie

D. To count the total words stored in the Trie

Solution

1. Step 1: Understand the insert operation

   The insert operation adds each character of a word into the Trie one by one, creating nodes if they don't exist.

2. Step 2: Compare with other operations

   Deleting removes words, searching checks presence, counting totals words. Insert specifically adds words.

3. Final Answer:

   To add a new word character by character into the Trie -> Option B

4. Quick Check:

   Insert = Add word stepwise [OK]

Hint: Insert means adding word letters step-by-step [OK]

Common Mistakes:

• Confusing insert with search or delete
• Thinking insert counts words
• Assuming insert removes words

2. Which of the following is the correct way to start inserting a word "cat" into an empty Trie in Python?

easy

A. for char in "cat": current = current.children[char] if char in current.children else current.children[char] = TrieNode()

B. for char in "cat": current = current.children[char]

C. for char in "cat": current.children[char] = TrieNode(); current = current.children[char]

D. for char in "cat": if char not in current.children: current.children[char] = TrieNode(); current = current.children[char]

Solution

1. Step 1: Check condition before adding node

   We must check if the character node exists before creating a new one to avoid overwriting.

2. Step 2: Move current pointer correctly

   After ensuring the node exists, move current to that child node for next character insertion.

3. Final Answer:

   for char in "cat": if char not in current.children: current.children[char] = TrieNode(); current = current.children[char] -> Option D

4. Quick Check:

   Check existence then add and move [OK]

Hint: Check if node exists before adding new one [OK]

Common Mistakes:

• Not checking if child node exists before assignment
• Not moving current pointer after insertion
• Overwriting existing nodes

3. Consider the following code snippet for inserting the word "dog" into a Trie. What will be the printed output after insertion?

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

root = TrieNode()

word = "dog"
current = root
for char in word:
    if char not in current.children:
        current.children[char] = TrieNode()
    current = current.children[char]
current.is_end = True

print(list(root.children.keys()))

medium

A. ['d']

B. ['o']

C. ['g']

D. []

Solution

1. Step 1: Insert characters one by one

   The first character 'd' is added as a child of root, so root.children has key 'd'.

2. Step 2: Check what is printed

   Printing root.children.keys() shows the first level keys, which is ['d'] after insertion.

3. Final Answer:

   ['d'] -> Option A

4. Quick Check:

   Root children keys after insert = ['d'] [OK]

Hint: Root children keys show first inserted letters [OK]

Common Mistakes:

• Expecting all letters at root level
• Printing keys of last node instead of root
• Confusing keys with values

4. The following code attempts to insert the word "bat" into a Trie but has a bug. What is the error?

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

root = TrieNode()
word = "bat"
current = root
for char in word:
    current.children[char] = TrieNode()
current = current.children[char]
current.is_end = True

medium

A. The children dictionary is not initialized

B. The is_end flag is set before inserting all characters

C. The current pointer is moved outside the loop, causing nodes to not be chained properly

D. The loop variable 'char' is not defined

Solution

1. Step 1: Analyze loop and pointer movement

   The line moving current pointer is outside the loop, so current only moves after loop ends, not per character.

2. Step 2: Understand effect on insertion

   Nodes for each character are created directly under root (no chaining), and only the last node's is_end is set.

3. Final Answer:

   The current pointer is moved outside the loop, causing nodes to not be chained properly -> Option C

4. Quick Check:

   Pointer must move inside loop to build chain [OK]

Hint: Move current pointer inside loop to link nodes [OK]

Common Mistakes:

• Moving pointer outside loop
• Not creating nodes conditionally
• Setting is_end too early

5. You want to insert multiple words ["apple", "app", "ape"] into a Trie. After insertion, which of the following statements is TRUE about the Trie structure?

hard

A. The node for 'l' after "app" exists only for "apple"

B. The node for 'p' after 'ap' will have is_end = True for both "app" and "ape"

C. Each word creates a completely separate branch from root

D. The root node's is_end flag will be True after insertion

Solution

1. Step 1: Understand shared prefixes in Trie

   Words "apple", "app", and "ape" share prefix "ap"; nodes for 'a' and 'p' are shared.

2. Step 2: Check is_end flags for words

   "app" ends at second 'p' node, so that node's is_end = True; "apple" continues to 'l' and 'e', so 'l' node is not end, but 'e' node is end.

3. Step 3: Analyze options

   The node for 'p' after 'ap' will have is_end = True for both "app" and "ape" is wrong because 'p' node cannot be end for both "app" and "ape"; 'ape' ends at 'e' node. Each word creates a completely separate branch from root is wrong because branches share prefix nodes. The root node's is_end flag will be True after insertion is wrong because root node is not end of any word.

4. Final Answer:

   The node for 'l' after "app" exists only for "apple" -> Option A

5. Quick Check:

   Shared prefix nodes, is_end marks word ends [OK]

Hint: Shared prefixes share nodes; is_end marks word ends only [OK]

Common Mistakes:

• Assuming each word has separate root branch
• Marking is_end on wrong nodes
• Setting root is_end True incorrectly