A trie (also called a prefix tree) is a tree structure built specifically for storing strings. Instead of storing an entire key at a single node, a trie spreads a string across a path: each edge or node position corresponds to one character, and a word is represented by the sequence of characters encountered from the root down to a node marked as the end of a word. Because strings that begin the same way share the same initial path, tries naturally group words by common prefix.
This matters in COP3530 because tries trade memory for predictable speed. Lookup in a balanced BST costs O(log n) comparisons of whole strings, while a trie lookup costs roughly O(m) steps for a string of length m, independent of how many words are stored. That makes tries the structure behind autocomplete, spell-checking, IP routing tables, and dictionary word games. The cost is space: every node may hold an array or map of child pointers, one slot per possible character.
As you watch, pay close attention to four things: how a node is represented (child array versus hash map, plus the end-of-word flag), how insertion walks down the tree creating nodes only when a child is missing, how search distinguishes "this prefix exists" from "this complete word exists," and how deletion must avoid removing nodes that are still needed by other words. Try tracing a small word set such as cat, car, card, and dog by hand on paper, then check your drawing against the walkthroughs in the videos.
A full lesson on the trie data structure that works through insertion, deletion, and searching, as the title indicates. Expect the node structure to be introduced first, followed by step-by-step traversal of each operation. Deletion in particular is given explicit attention, which many shorter trie introductions skip.
At 18 minutes it is the most complete of the three, and it is the only one that explicitly covers deletion alongside insertion and search, so it maps directly onto the construction, insertion, and lookup subtopics.
Revisit this one after the Java implementation if the node representation still feels unclear, since it approaches the same structure from a more language-neutral angle. Watching the operations twice, from two explanations, is an efficient way to lock in the traversal pattern.
Repeated exposure from a different instructor is a practical way to confirm you have the insertion and search traversals correct rather than merely familiar.
Geekific's treatment of tries and prefix trees, explained conceptually and then implemented in Java with worked examples. It is framed as an advanced data structures lesson, so expect attention to how the node class holds its children and end-of-word marker. The GitHub repository linked in the description holds the accompanying code.
The explicit prefix-tree framing and Java implementation make it the best fit for the prefix-based searching subtopic and for students who want to see trie code in a language close to course assignments.
Together these videos target MO4 most directly: each one builds a trie from a set of strings and traces character-by-character traversal for insertion and search, which is exactly the skill you must demonstrate. They also support MO1, since seeing that trie lookup depends on string length rather than the number of stored keys clarifies why tries sidestep the degradation that plagues unbalanced binary search trees on string data. Finally, the discussion of child arrays, node counts, and memory overhead in these walkthroughs gives you the evidence needed for MO5, where you must weigh a trie's O(m) search time against its space cost and justify choosing it over an AVL tree or heap for a given problem.
These videos were chosen from YouTube on October 2, 2026. Each has captions; the player turns them on. Videos on YouTube can be changed or removed — if one no longer plays, tell your instructor. If a player does not appear, use its Watch on YouTube link.