Tries

A trie is a tree-like data structure in which data is stored in association with keys, which are typically strings. Tries are made of nodes, usually consisting of an array of pointers to other nodes and one other field that gives the programmer more information about the node and indicates if that node represents a key. Tries use large amounts of memory, but trade this for constant time (O(1)) lookup and insertion. In this section, we will discuss the basics of tries, and see an example for their implementation, in a dictionary.

• Lecture

  • Watch on Youtube
  • Watch on the CS50 Video Player
  • Download Lecture
  • Lecture Notes

• Shorts

  • Tries
  • Tries (Kevin)

• Supplementary Resources

  • Julia Geist on The Trie Data Structure (Prefix Tree)
  • Joseph Crick on Practical Data Structures for Frontend Applications: When to Use Tries
  • Vaidehi Joshi on Trying to Understand Tries

• Thought Questions

  • Why can we say that tries have constant time lookup and insertion?
  • What real world situations could a trie be useful for besides a dictionary?
  • What are the trade-offs involved in using a trie, and what are situations where one side matters more than the other?

• Problem

  • Autocomplete