Trie: Traversals

Tasks

Create a new branch in your data structures repository called trie-traversal. Add the following method:

• trie.traversal(start): Perform a full depth-first traversal of the graph beginning at start. The argument “start” should be a string, which may or may not be the beginning of a string or strings contained in the Trie.

Return a generator containing all tokens in the trie; Can be an empty string, which would then be a full depth-first traversal of the entire tree.

Your work should include unit tests that fully demonstrate the method you’ve added. Make sure to cover expected and edge cases. Add documentation of your new methods to your README file. Include any sources or collaborations.

Each method you are required to implement must also include the time complexity in Big O notation in your README.

Submission

Do your work on a branch. When you are finished and all your tests are passing, create a new pull request back to master from your trie-traversal branch and submit the URL for that pull request.

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