Trie insertion and search in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Trie data structure?

A Trie is a tree-like data structure used to store a dynamic set of strings where keys are usually strings. It allows fast retrieval of words by storing characters in nodes along paths.

beginner

How does insertion work in a Trie?

Insertion adds a word by creating nodes for each character if they don't exist, following the path from the root. The last node is marked to show the end of a word.

beginner

What does searching in a Trie involve?

Searching checks each character of the word by moving through nodes. If all characters are found and the last node is marked as a word end, the word exists in the Trie.

intermediate

Why is Trie efficient for prefix searches?

Because nodes represent characters in order, all words sharing a prefix share the same path. This makes finding all words with a prefix very fast.

intermediate

What is the time complexity of inserting or searching a word in a Trie?

Both insertion and search take time proportional to the length of the word, usually O(m), where m is the number of characters in the word.

What does each node in a Trie typically represent?

A A sentence

B A whole word

C A number

D A character of a word

Each node in a Trie represents a single character of a word.

When inserting a word into a Trie, what happens if a character node already exists?

A Skip to the next character node

B Delete the existing node

C Create a new node anyway

D Mark the node as a word end immediately

If the character node exists, insertion moves to that node to continue with the next character.

How do you know a word ends in a Trie node?

A The node is the root

B The node has no children

C The node has a special marker or flag

D The node stores the word length

A node is marked with a flag to indicate the end of a valid word.

What is the main advantage of using a Trie over a list for word search?

A Uses less memory

B Faster search by prefix

C Simpler to implement

D Stores numbers better

Tries allow very fast prefix searches compared to lists.

What is the worst-case time complexity to search a word of length m in a Trie?

A O(m)

B O(m^2)

C O(log m)

D O(1)

Searching takes time proportional to the length of the word, O(m).

Explain how to insert a word into a Trie step-by-step.

Think about walking through the word's letters and building the path.

Describe how searching for a word in a Trie works and how you know if the word exists.

Imagine tracing the word letter by letter in the Trie.

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