Trie Insert Operation in DSA C - Execution Trace

Concept Flow - Trie Insert Operation

Start at root node

↓

For each character in word

↓

Check if child node exists

↓

Move to child

↓

Repeat for next character

↓

Mark last node as end of word

↓

Done

Start at the root. For each letter, check if a child node exists. If yes, move there; if no, create it. At the end, mark the node as a word end.

Execution Sample

DSA C

insert(root, "cat") {
  node = root;
  for each char in "cat":
    if child not exist: create child
    node = child
  mark node as end
}

Inserts the word "cat" into the trie by creating nodes for letters if missing and marking the last node.

Execution Table

Step	Operation	Current Character	Nodes in Trie	Pointer Changes	Visual State
1	Start insertion	-	root node only	current = root	┌─────┐ │root │ │next:∅│ └─────┘
2	Check 'c' child	c	root node only	No child 'c', create node 'c' current = node 'c'	┌─────┐ ┌─────┐ │root │──→ │ 'c' │ │next:─┼ │next:∅│ └─────┘ └─────┘
3	Check 'a' child	a	root, 'c'	No child 'a' in 'c', create node 'a' current = node 'a'	┌─────┐ ┌─────┐ ┌─────┐ │root │──→ │ 'c' │──→ │ 'a' │ │next:─┼ │next:─┼ │next:∅│ └─────┘ └─────┘ └─────┘
4	Check 't' child	t	root, 'c', 'a'	No child 't' in 'a', create node 't' current = node 't'	┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │root │──→ │ 'c' │──→ │ 'a' │──→ │ 't' │ │next:─┼ │next:─┼ │next:─┼ │next:∅│ └─────┘ └─────┘ └─────┘ └─────┘
5	Mark end of word	-	root, 'c', 'a', 't'	Mark node 't' as end of word	┌─────┐ ┌─────┐ ┌─────┐ ┌────────────┐ │root │──→ │ 'c' │──→ │ 'a' │──→ │ 't' (end) │ │next:─┼ │next:─┼ │next:─┼ │next:∅ │ └─────┘ └─────┘ └─────┘ └────────────┘
6	Insertion complete	-	root, 'c', 'a', 't' (end)	No pointer changes	Final trie with word 'cat' inserted

💡 All characters processed; last node marked as end of word.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	Final
current	root	'c' node	'a' node	't' node	't' node (marked end)	't' node (marked end)
Trie Size (nodes)	1	2	3	4	4	4

Key Moments - 3 Insights

Why do we create a new node only if the child does not exist?

Because if the child node exists, it means that prefix is already in the trie. See execution_table rows 2-4 where new nodes are created only when missing.

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

Marking the last node tells us that a complete word ends here. Without this, we can't distinguish between prefixes and full words. See execution_table row 5.

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

We reuse existing nodes for the shared prefix and create new nodes only for the remaining characters. This is shown by checking child existence in execution_table steps.

Visual Quiz - 3 Questions

Look at the execution_table, what is the pointer 'current' pointing to after Step 3?

A 'a' node

B 'c' node

C 't' node

D root node

💡 Hint

Check the 'Pointer Changes' column in row for Step 3.

At which step is the node for character 't' created?

A Step 3

B Step 4

C Step 2

D Step 5

💡 Hint

Look at the 'Operation' and 'Current Character' columns in execution_table.

If the word 'cat' was already in the trie, how would the pointer changes differ?

A Only the last node marked as end again

B New nodes created for all characters

C No new nodes created; current moves through existing nodes

D Root pointer changes

💡 Hint

Refer to key_moments about reusing existing nodes for shared prefixes.

Concept Snapshot

Trie Insert Operation:
- Start at root node
- For each character:
  - If child exists, move to it
  - Else create new child node
- Mark last node as end of word
- Efficient prefix sharing
- No duplicate nodes for shared 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 yes, it moves to that child. If no, it creates a new node for that character and moves there. After processing all characters, it marks the last node as the end of a word. This process efficiently shares prefixes among words. The execution table shows each step, pointer changes, and the visual state of the trie nodes. 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 pointer positions and node creation steps.

Practice

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

easy

A. To add a word character by character into the Trie

B. To delete a word from the Trie

C. To search for a word in the Trie

D. To count the number of words in the Trie

Solution

1. Step 1: Understand the insert operation

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

2. Step 2: Differentiate from other operations

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

3. Final Answer:

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

4. Quick Check:

   Insert = Add word [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 declare a Trie node structure in C for insertion?

easy

A. typedef struct TrieNode { char* word; struct TrieNode* children[26]; } TrieNode;

B. typedef struct TrieNode { int data; struct TrieNode* next; } TrieNode;

C. typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode;

D. typedef struct TrieNode { struct TrieNode* left; struct TrieNode* right; } TrieNode;

Solution

1. Step 1: Identify Trie node components

   A Trie node has an array of pointers for children (26 letters) and a boolean to mark word end.

2. Step 2: Match with options

   typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode; matches this structure. Others describe linked list or binary tree nodes, not Trie nodes.

3. Final Answer:

   typedef struct TrieNode { struct TrieNode* children[26]; bool isEndOfWord; } TrieNode; -> Option C

4. Quick Check:

   Trie node = children array + end flag [OK]

Hint: Trie nodes have 26 children pointers and end-of-word flag [OK]

Common Mistakes:

• Using linked list node structure instead of array
• Confusing Trie with binary tree node
• Missing end-of-word boolean

3. What will be the output of the following C code snippet after inserting the word "cat" into an empty Trie and checking the isEndOfWord flag at the last node?

TrieNode* root = createNode();
insert(root, "cat");
bool flag = root->children['c' - 'a']->children['a' - 'a']->children['t' - 'a']->isEndOfWord;
printf("%d", flag);

medium

A. 0

B. Runtime error

C. Compilation error

D. 1

Solution

1. Step 1: Insert "cat" into Trie

   Each character creates or uses existing nodes. The last character 't' node's isEndOfWord is set to true (1).

2. Step 2: Check isEndOfWord flag

   Accessing the node for 't' and printing isEndOfWord prints 1 because the word ends there.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Inserted word end flag = 1 [OK]

Hint: End node flag is set to true after insert [OK]

Common Mistakes:

• Assuming isEndOfWord is 0 after insert
• Indexing children incorrectly
• Forgetting to set isEndOfWord during insert

4. Consider the following buggy insert function for a Trie in C:

void insert(TrieNode* root, const char* word) {
    TrieNode* node = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int index = word[i] - 'a';
        if (node->children[index] == NULL) {
            node->children[index] = malloc(sizeof(TrieNode));
        }
        node = node->children[index];
    }
    node->isEndOfWord = true;
}

What is the main bug in this code?

medium

A. New nodes are not initialized, leading to garbage values

B. The loop condition is incorrect and may cause infinite loop

C. The isEndOfWord flag is set too early

D. The root pointer is not updated after insertion

Solution

1. Step 1: Analyze node allocation

   New nodes are allocated with malloc but not initialized, so children pointers and isEndOfWord have garbage values.

2. Step 2: Consequences of uninitialized nodes

   Uninitialized children can cause incorrect behavior or crashes during further insert/search operations.

3. Final Answer:

   New nodes are not initialized, leading to garbage values -> Option A

4. Quick Check:

   Missing initialization = bug [OK]

Hint: Always initialize new Trie nodes after malloc [OK]

Common Mistakes:

• Ignoring initialization of new nodes
• Assuming malloc zeros memory
• Confusing loop condition correctness

5. You want to insert multiple words into a Trie and then count how many words start with the prefix "pre". Which modification to the Trie insert operation helps achieve this efficiently?

hard

A. Store the entire word at each node instead of characters

B. Add a counter in each node that increments every time a word passes through it during insertion

C. Only mark isEndOfWord without any counters

D. Use a linked list instead of an array for children nodes

Solution

1. Step 1: Understand prefix counting

   To count words with a prefix, each node can keep a count of how many words pass through it.

2. Step 2: Modify insert to update counters

   During insertion, increment the counter at each node visited. Then prefix count is the counter at prefix's last node.

3. Final Answer:

   Add a counter in each node that increments every time a word passes through it during insertion -> Option B

4. Quick Check:

   Prefix count = node counters [OK]

Hint: Use counters in nodes to track prefix occurrences [OK]

Common Mistakes:

• Not using counters, making prefix count slow
• Storing full words at nodes wastes space
• Using linked list slows access