Implement a Trie in Python

Tasks

Create a new branch in your data structures repository called``trie``. You will use this branch to do your work for this assignment. Add a new file to your data structures repository. Call it trie.py. In this file, implement a Trie as a Python class (or classes). Your trie should have the following methods:

  • insert(self, token): will insert the value token into the trie.

If character in token is already present, it will be ignored. * contains(self, token): will return True if token is in the trie, False if not.

Your trie implementation must include tests. The tests, as usual for our data structures, must run both in Python 2.7 and Python 3.5. Ensure that your tests are properly connected to Travis CI and that you have a travis badge displayed on your README.

Expand your README to include notes about the trie you’ve constructed. Include any sources or collaborations.

Submitting Your Work

When you’ve completed your work and all your tests are passing, submit a pull request from the trie branch back to master. Copy the URL for that pull request and submit it using the URL input. When that is done, you may merge your branch back to master.

As usual, use the comment function to submit questions, comments and reflections on the work you’ve done here.