26.1.6. Tries (Prefix Trees)

Try these first

1. 1.

   What is the main advantage of using a trie data structure?

   Hint

   Consider the aspect of prefix searching.

2. 2.

   True or False: Each node in a trie can represent a string.

   Hint

   Think about the composition of a word.

3. 3.

   What operation has a time complexity of O(length of the word) in a trie?

   • Insertion
   • Search
   • Deletion

   Hint

   Think about the main operations of tries.

4. 4.

   True or False: A trie is good for operations that require a lot of prefix searching.

   • True
   • False

   Hint

   Consider what a trie is built to do.

5. 5.

   Given a list of words, implement a trie structure from it. Write the insert method in a programming language of your choice.

   Hint

   Remember to handle the creation of new nodes correctly for each character.

6. 6.

   Analyze the space efficiency of a trie compared to an array. Provide a detailed explanation.

   Hint

   Think about how prefixes can reduce the number of unique nodes compared to individual string storage.