Overview

The first special kind of tree that we’ll consider is called a “prefix tree” or a “trie” (pronounced like “try”). This tree is an alternative way of storing words that leverages the fact that many words share common starting characters.

Basic Learning Objectives

Before class, you should be able to:

  • Describe what a prefix tree is
  • Describe the operations of a prefix tree

Advanced Learning Objectives

After class, you should be able to:

  • Understand prefix tree operations and their implementations in Kotlin
  • Analyze the run-time of prefix tree operations

Resources

You should read the following:

Checks

Submit answers to the following on Moodle. Drawing out the prefix trees will be tedious, so feel free to draw out your answers, take a picture or screenshot, and put it on Moodle.

  1. Draw the prefix tree after inserting the following words: “bad”, “ban”, “me”, “met”, “mess”, and “data”.
  2. Based on your answer to Q1, draw the prefix tree tree after deleting “me”.
  3. Based on your answer to Q2, draw the prefix tree after deleting “ban”
  4. Based on your answer to Q3, draw the prefix tree after deleting “data”

Acknowledgements

Check question from Prof. Jean Salac.