Implementing Tries in Python
Lesson 1 of 2
  1. 1
    Introduction
    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…
    Start
  2. 2
    The Trie Node
    Let’s define the TrieNode class we will use to implement a trie. To represent subsequent characters in a string, a TrieNode object contains a dictionary that maps a character to an instance of Tri…
    Start
  3. 3
    Adding a String to a Trie
    In this exercise, we will describe the algorithm that adds a word to a trie. We will then implement this algorithm in the add_string() function of the Trie class. We will be implementing this algor…
    Start
  4. 4
    Searching for a String in a Trie
    In this exercise, we will search for a string in a trie. A string is loaded into a trie for one of two reasons: * The trie represents a dictionary of words. * The string contains some relevant info…
    Start
  5. 5
    Searching for a Prefix in a Trie
    In this exercise, we will work on the count_prefix() method in our Trie class. As its name suggests, this function will count the number of words with a prefix up to some character. We track this c…
    Start
  6. 6
    Using a Trie
    Now that you have finished constructing your trie data structure, in this exercise, you will get a chance to see it in action. In the following checkpoints, you will add strings, search for string…
    Start
  7. 7
    Review
    Great job on making it this far in the lesson on Tries! This is a very powerful data structure with many applications in software engineering, computer science, and coding interviews! Let’s summar…
    Start

How you'll master it

Stress-test your knowledge with quizzes that help commit syntax to memory