CODEWITHSUNDEEP
pythonooptrie
Shannon
Shannon

Reputation: 1205

What does use of TrieNode data structure in TrieNode class mean?

I saw the following piece of code in many trie questions where the class is used inside itself as a defaultdict data structure. I understand that it means that children is dictionary of TrieNode. However, I do not understand the base case (the very last child). There is no None or empty definition for it. I was wondering if someone can explain it.

class TrieNode():
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.isWord = False

Upvotes: 0

Views: 1091

Answers (2)

Aashish A
Aashish A

Reputation: 111

Trie is usually used for searching a given string from a set of strings dynamically. Each string will consist of a finite no of possible characters which is stored in self.children. So each preceding character is connected to its succeeding characters through self.children and each character is a key and each value is a TrieNode object.

Consider words {"can", "cancel"}. The trie constructed for these words will be: c-a-n-c-e-l. Since both words have same prefix, they have the same sequence of characters. The isWord flag is used for checking if a character is the end of a word found in our set so the isWord flag of characters n and l will be true. Thus n and all its preceding characters form a word in our set

If a character is the last character of a word and no other words have the same prefix (base case), it will have no children so self.children will be an empty dictionary == {}.

Upvotes: 1

Greg Ward
Greg Ward

Reputation: 1673

It's a recursive data structure, commonly used for trees. Makes sense for tries too, I guess.

In this case, if self.children is empty (i.e. len(self.children) == 0), the data structure bottoms out. That's when you have reached the "end" of the trie. Well, really, one end of it.

Upvotes: 2

Related Questions