Tries

Question 1

Trie

Answer 1

• Tree-based data structure
• Used to implements sets or maps
• Each node in the tree is a letter in the key
• Each node stores an array of pointers to all possible letters in key
  
  • If keys are words, each node stores alphabet array
  • If keys are numbers, each node stores 10-digit array
• Value of each node is value (in key/val pair) or flag indicating membership (in set)
• All operations a O(k), length of the word

Question 2

Trie

Implementation

Answer 2

• Implemented with nodes and pointers
• Each node stores:
  
  • an array of pointers
  • an isComplete flag
• Root’s isComplete flag doesn’t mean anything

Question 3

Trie

Remove

Answer 3

• Implemented recursively
• Finds the word, and then deletes nodes while backtracking

Steps

1. Create pointer to letter in word, starting at -1 (because you start at root)
2. Check if progress through word equals length of word
3. If so..
   
   • Check if word is present in trie
   • If so, check number of children (loop through array pointers)
   • If no kids, return true delete bool
4. If not, increment pointer in word
5. Check if child node exists
6. Perform remove on child node
7. If del bool == true, delete pointer to child
8. If node is a word, or has additional children, set del bool to false
9. Return del bool

Complexity

Time

Best ⇔ Average ⇔ Worst: O(k)

Space

O(1)

* k is the length of the longest word

Question 4

Trie

Print in Order

Answer 4

• Use pre-order traversal to print in lexographical order

Question 5

Trie

Insert

Answer 5

• Loop through each letter in word
• Find child based on index of letter in array
• Create new child nodes as neccessary
• Exit loop, set isComplete flag to true