Trie Insert Operation in DSA Python - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if char node exists

↓

Move to char node

↓

Repeat for next char

↓

Mark last node as end of word

↓

Done

Insert each character of the word into the trie, creating nodes if missing, then mark the last node as end of word.

Execution Sample

DSA Python

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

root = TrieNode()
word = "cat"

Insert the word 'cat' into an empty trie step-by-step.

Execution Table

Step	Operation	Current Char	Node Created	Pointer Changes	Trie Visual State
1	Start insertion at root	-	No	root pointer at root node	root: {}
2	Check 'c' in root.children	c	No	root.children['c'] = new node	root: {c: Node}
3	Move to node 'c'	c	No	current pointer moves to node 'c'	root: {c: Node} node c: {}
4	Check 'a' in node 'c'.children	a	No	node c.children['a'] = new node	root: {c: Node} node c: {a: Node}
5	Move to node 'a'	a	No	current pointer moves to node 'a'	root: {c: Node} node c: {a: Node} node a: {}
6	Check 't' in node 'a'.children	t	No	node a.children['t'] = new node	root: {c: Node} node c: {a: Node} node a: {t: Node}
7	Move to node 't'	t	No	current pointer moves to node 't'	root: {c: Node} node c: {a: Node} node a: {t: Node} node t: {}
8	Mark node 't' as end of word	-	No	node t.is_end = True	root: {c: Node} node c: {a: Node} node a: {t: Node (end)}
9	Insertion complete	-	No	Return to caller	Trie contains word 'cat'

💡 All characters inserted and last node marked as end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
current_node	root	node 'c'	node 'a'	node 't'	node 't' (is_end=True)	node 't' (is_end=True)
root.children	{}	{'c': Node}	{'c': Node}	{'c': Node}	{'c': Node}	{'c': Node}
node 'c'.children	N/A	{}	{'a': Node}	{'a': Node}	{'a': Node}	{'a': Node}
node 'a'.children	N/A	N/A	{}	{'t': Node}	{'t': Node}	{'t': Node}
node 't'.is_end	N/A	N/A	N/A	False	True	True

Key Moments - 3 Insights

Why do we create a new node only if the character is not already present?

Because if the character node exists, we just move to it to continue insertion. Creating a new node only when missing avoids overwriting existing paths. See execution_table steps 2, 4, and 6 where new nodes are created only if absent.

Why do we mark the last node as end of word?

Marking the last node as end of word tells us that a complete word ends here, distinguishing prefixes from full words. See execution_table step 8 where node 't' is marked is_end=True.

What happens if we insert a word that shares prefix with existing words?

We reuse existing nodes for shared prefix characters and create new nodes only for new characters. This saves space and time. The execution_table shows this by moving current pointer along existing nodes before creating new ones.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what happens when checking character 'a'?

A The current pointer moves to node 'a' without creating a new node.

B A new node for 'a' is created under node 'c'.

C The insertion stops because 'a' is missing.

D The root node is replaced.

💡 Hint

Check the 'Node Created' and 'Pointer Changes' columns at step 4 in execution_table.

At which step is the last node marked as end of word?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look for 'Mark node as end of word' operation in execution_table.

If the word was 'car' instead of 'cat', how would the trie visual state differ at step 6?

A Node 'c' would have child 'r' directly.

B Root would have child 'r'.

C Node 'a' would have child 'r' instead of 't'.

D No nodes would be created.

💡 Hint

Compare the 'Current Char' and 'Trie Visual State' columns at step 6 for 'cat' and imagine replacing 't' with 'r'.

Concept Snapshot

Trie Insert Operation:
- Start at root node.
- For each character, check if child node exists.
- If not, create new node.
- Move current pointer to child node.
- After last char, mark node as end of word.
- Efficiently stores words sharing prefixes.

Full Transcript

The Trie Insert Operation starts at the root node. For each character in the word, it checks if a child node exists. If missing, it creates a new node. Then it moves the current pointer to that child node. After processing all characters, it marks the last node as the end of the word. This process efficiently stores words by sharing common prefixes, saving space. The execution table shows each step, including node creation and pointer moves. Key moments clarify why nodes are created only when missing and why marking the end of word is important. The visual quiz tests understanding of these steps.

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