educative.io

Rebuilding Trie

Courses
,
#1

Hi @Design_Gurus ,

While rebuilding the Trie, how are the count of terminal nodes calculated as they are not present in serialized form ? Does this mean that count will be calculated again as and when Users start searching words after the Trie is Deserialized from file?

Course: Grokking the System Design Interview - Learn Interactively
Lesson: Designing Typeahead Suggestion - Grokking the System Design Interview

Course: Grokking the System Design Interview - Learn Interactively
Lesson: Designing Typeahead Suggestion - Grokking the System Design Interview

Course: Grokking the System Design Interview - Learn Interactively
Lesson: Designing Typeahead Suggestion - Grokking the System Design Interview

#2

Hi @Akshay_Kulkarni, thanks for reaching out.

  1. As the saving pattern for trie is “C2,A2,R1,T,P,O1,D”, in this pattern each node with no value means that it’s a terminal node.
  2. yes, terminal nodes can be counted while searching a word because the searching algorithm works in a recursive call, so we can iterate on each terminal node and then count them.
1 Like