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.