Trie insertion and search in Data Structures Theory - Step-by-Step Execution

Concept Flow - Trie insertion and search

Insert/Search first char

↓

Node exists?

No→Create new node

↓

Link new node

↓

Move to next char

↓

Repeat until word end

↓

Mark end of word (insertion) or Return found/not found (search)

For each character in the word, check if a node exists. If not, create it. Move to the next character until the word ends. Mark the end for insertion or check for presence in search.

Execution Sample

Data Structures Theory

Insert 'cat'
Insert 'car'
Search 'cat'
Search 'cap'

Insert two words 'cat' and 'car' into the trie, then search for 'cat' and 'cap'.

Analysis Table

Step	Operation	Current Char	Node Exists?	Action	Trie State (Visual)
1	Insert	'c'	No	Create node 'c'	∅ → c
2	Insert	'a'	No	Create node 'a' under 'c'	c → a
3	Insert	't'	No	Create node 't' under 'a'	c → a → t (end)
4	Insert	'r'	No	Create node 'r' under 'a'	c → a → t (end), a → r (end)
5	Search	'c'	Yes	Move to node 'c'	c → a → t, a → r
6	Search	'a'	Yes	Move to node 'a'	c → a → t, a → r
7	Search	't'	Yes	Move to node 't'	c → a → t (end), a → r
8	Search	End of word	Yes	Word found (end marked)	c → a → t (end), a → r
9	Search	'c'	Yes	Move to node 'c'	c → a → t (end), a → r
10	Search	'a'	Yes	Move to node 'a'	c → a → t (end), a → r
11	Search	'p'	No	Node 'p' missing, word not found	c → a → t (end), a → r

💡 Search stops when all characters are found and end of word is marked, or when a character node is missing.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11
Current Node	Root (empty)	Node 'c'	Node 'a'	Node 't'	Node 'r'	Node 'c'	Node 'a'	Node 't'	End	Node 'c'	Node 'a'	None
Trie Size (nodes)	0	1	2	3	4	4	4	4	4	4	4	4
Word Found Flag	False	False	False	False	False	False	False	False	True	False	False	False

Key Insights - 3 Insights

Why do we create new nodes only when the character node does not exist?

Because existing nodes represent prefixes already stored. Creating new nodes only when missing avoids duplicates and keeps the trie compact, as shown in steps 1-4 of the execution_table.

How do we know a word ends in the trie?

We mark the last node of the inserted word as an 'end' node. During search (step 8), finding this mark confirms the word exists.

Why does the search fail at step 11 for 'cap'?

Because the node for character 'p' does not exist under 'a', so the trie cannot match the word fully, indicating 'cap' is not stored.

Visual Quiz - 3 Questions

Look at the execution_table at step 4. What is the trie state after inserting 'car'?

A c → a → t (end), a → r (end)

B c → a → r (end)

C c → a → t → r (end)

D c → r → a (end)

💡 Hint

Refer to the 'Trie State (Visual)' column at step 4 in the execution_table.

At which step does the search confirm the word 'cat' is found?

A Step 7

B Step 6

C Step 8

D Step 11

💡 Hint

Check the 'Word Found Flag' in variable_tracker and the 'Action' column in execution_table.

If we tried to insert 'cap' after 'cat' and 'car', what would happen at step 11?

A Search would fail at 'p'

B Node 'p' would be created under 'a'

C Node 't' would be replaced by 'p'

D Word would be marked as not found

💡 Hint

Insertion creates missing nodes; step 11 shows search fails because 'p' node is missing.

Concept Snapshot

Trie insertion and search:
- Insert: For each char, create node if missing
- Search: For each char, move if node exists
- Mark end of word on insertion
- Search success if all chars found and end marked
- Efficient prefix-based storage and lookup

Full Transcript

A trie stores words by creating nodes for each character. When inserting, we check if a node for the current character exists. If not, we create it and link it under the previous node. We repeat this for all characters and mark the last node as the end of a word. Searching follows the same path: for each character, we move to the corresponding node if it exists. If all characters are found and the last node is marked as an end, the word exists. If any character node is missing, the search fails. This method efficiently stores and searches words by their prefixes.

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