In the article, we introduced the prefix tree data structure (better known as a trie), its properties, and some of its applications. In this lesson, we will see how we can implement a trie.
Recall that a trie is an efficient way to store a collection of strings by storing them in a tree-like data structure.
We will create a Python object that will represent the trie data structure. This object will contain functions to store a word, search for a word, and count the number of words that contain a particular prefix.
We will also create a Python object that represents a node in the trie.
We will construct the Python class to the right and define all necessary functions. Then we will see an application of the trie as a spell checker.