A binary search tree (BST) organizes data so that, at every node, all keys in the left subtree are smaller and all keys in the right subtree are larger. That single ordering invariant is what makes search, insertion, and deletion feel fast: at each step you discard half of the remaining possibilities, much like binary search on a sorted array. Before moving on to AVL trees, heaps, and tries, we need to be precise about what a BST guarantees and, just as importantly, what it does not.
The catch is that BST performance depends on shape, not just on size. Operations cost O(h), where h is the height of the tree. A well-proportioned tree over n keys has height around log n, but a tree built by inserting already-sorted (or reverse-sorted) data degenerates into a path essentially a linked list and height becomes n. This is the gap between the average case and the worst case that motivates every structure in this module: if we can force the tree to stay shallow, we get logarithmic behavior regardless of input order.
As you watch, keep three questions in mind. First, how is each operation (search, insert, delete) expressed recursively in terms of the ordering invariant? Second, where exactly does the cost of an operation come from, and how does it relate to height? Third, which insertion sequences produce balanced versus degenerate trees? Try sketching a few insertion orders on paper and comparing the resulting shapes before you reach the AVL material.
An introductory lecture on binary search trees that defines the BST ordering property and walks through the structural rules that distinguish a BST from an arbitrary binary tree. Based on its title and description, it covers the core vocabulary (root, subtree, ordered/sorted binary tree) and the basic properties you rely on when searching. Expect worked examples that show how the ordering invariant guides traversal down the tree.
This is the right starting point for the Binary Search Tree Fundamentals subtopic: it builds the vocabulary and the invariant that everything else in the module depends on, from a widely watched channel known for slow, example-driven explanations.
A code-focused treatment that explains BST concepts and then implements them in Java, with examples and a linked GitHub repository. It is likely to walk through node structure and the insert, search, and delete routines, including the trickier delete cases such as removing a node with two children. The implementation view connects the abstract ordering rule to concrete recursive code.
Seeing the operations as actual code reinforces why each operation follows a single root-to-leaf path, which is exactly the observation that makes the height-dependence argument click; Geekific's implementation walkthroughs pair well with the more conceptual video above.
A short lecture devoted specifically to the asymptotic (big-O) efficiency of BST operations, presented with slides by a university instructor. It should establish that search, insert, and delete all cost O(h) and then analyze what h can be, contrasting the balanced case with the degenerate case. This is the analytical complement to the two implementation-oriented videos.
It directly serves the Time Complexity, Tree Imbalance, and Worst-Case Degenerate Trees subtopics, and because it comes from a course lecture it uses the same formal big-O framing we expect in your written analyses.
Together these three videos establish the baseline that the rest of the module builds on. The first two give you the structural definition and a concrete implementation of BST search, insert, and delete, so you can reason about operations as traversals along a single path; the third converts that observation into an explicit O(h) analysis and shows how h collapses to n in a degenerate tree. That is precisely the argument MO1 asks you to be able to make, and it supplies the baseline complexity figures you will compare against when evaluating AVL trees, heaps, and tries under MO5. The balance problem identified here is also the direct motivation for the rotation-based repair operations you will trace in MO2 and for the shape invariants that make heap and trie operations predictable in MO3 and MO4.
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.
A binary search tree gives you O(log n) search, insert, and delete only when it stays reasonably short. Insert keys in sorted or nearly sorted order and the same tree degenerates into what is essentially a linked list, pushing every operation to O(n). AVL trees fix this by adding one simple rule: for every node, the heights of its left and right subtrees may differ by at most one. That difference is the node's balance factor, and whenever an insertion or deletion violates the rule, the tree repairs itself with local restructuring operations called rotations.
In this topic you will learn the AVL definition and its height guarantee, how to compute and update balance factors, and the four repair cases: single left and single right rotations for the "straight line" imbalances, and the left-right and right-left double rotations for the "zig-zag" cases. Insertion requires at most one rotation (single or double) to restore balance; deletion may require rebalancing at several nodes along the path back to the root, which is why it is treated separately.
The three videos below form a short, ordered sequence: definition and search, then insertion, then deletion. While watching, keep a pen handy and redraw each example yourself. Focus on three things: which node is the first unbalanced ancestor, which of the four cases applies based on the direction of the imbalance, and how heights and balance factors are updated after the rotation. Pausing to predict the rotation before the narrator performs it is the fastest way to build fluency for exams.
A compact introduction to AVL trees that defines the structure and walks through the search operation. Expect the balance condition, the role of node heights, and why searching an AVL tree works exactly like searching an ordinary BST but with a guaranteed O(log n) bound. Linked source code is provided on the channel's GitHub repository.
Michael Sambol's data structures series is a widely used, carefully scripted set of explanations, and this video covers the "motivation," "definition and properties," and "balance factor" subtopics before any rotation mechanics are introduced.
The longest video of the three, devoted to AVL insertion. It should cover how a new key is inserted as in a normal BST, how the imbalance is detected on the way back up, and how the rotation cases are chosen and applied to restore the AVL invariant.
Insertion is where single and double rotations are introduced most naturally, and the extra running time here gives room for worked examples of the left-left, right-right, left-right, and right-left cases you must be able to trace.
A focused treatment of AVL deletion. It should show the standard BST removal cases (leaf, one child, two children with a successor or predecessor) and then the rebalancing that follows, including the fact that deletion can require rotations at more than one ancestor.
Deletion is the subtopic students most often skip, and this video completes the set from the same instructor so the notation, diagrams, and terminology match the previous two videos exactly.
Together these videos directly serve MO1 and MO2. The first establishes why unbalanced BSTs degrade and what structural invariant AVL trees impose to prevent it, supporting the AVL portion of MO1. The insertion and deletion videos give you worked traces of the balance factor check and the single and double rotations needed to restore it, which is precisely the skill MO2 asks you to demonstrate. The height guarantee discussed throughout also supplies the O(log n) reasoning you will reuse when comparing AVL trees against heaps and tries for MO5; heaps and tries themselves (MO3, MO4) are covered elsewhere in the module.
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.
An AVL tree is a binary search tree that enforces a balance invariant: for every node, the heights of its left and right subtrees differ by at most one. That single structural guarantee is what turns the shaky worst case of an ordinary BST into a dependable one. Because the height of an AVL tree with n keys stays proportional to log n, search, insert, and remove are all O(log n) in the worst case, not just on average.
This topic asks you to reason about that guarantee rather than just state it. You will look at where the log n bound comes from, what the extra balance information costs in memory (a height or balance factor stored per node, plus the rotations performed during updates), and how AVL trees compare to plain BSTs, to other balanced trees such as red-black trees, and to hash tables. Each comparison has a different flavor: plain BSTs are cheaper to update but can degrade to a linked list on sorted input; red-black trees rebalance less aggressively and so insert slightly faster but search slightly slower; hash tables beat both on average lookup time but give up ordering and worst-case predictability.
As you watch, keep two questions in front of you. First, is the claim being made about the average case or the worst case? That distinction is the whole argument for AVL trees in lookup-intensive and latency-sensitive systems, where a predictable upper bound matters more than a good average. Second, what does the structure give up to earn its guarantee? Write down the trade-off in your own words for each structure you see, because the final learning outcome in this module is about justifying a choice, not memorizing a table.
A focused analysis of the cost of AVL tree operations, arguing that search, insert, and remove each run in O(log n) time. Based on the title and description, it works through why the balance condition bounds the tree's height and how that bound carries over to the three core operations, contrasting the result with the slower behavior possible in an unbalanced tree.
This is the most direct match for the time-complexity subtopic, and it comes from a university instructor presenting the reasoning behind the bound rather than just asserting it, which is what you need in order to defend the claim yourself.
A visual side-by-side tour of five related structures: binary search trees, AVL trees, red-black trees, splay trees, and heaps. The video is likely to show how each structure behaves on the same operations and where their performance and balancing strategies differ, using animations rather than formal proofs.
It places the AVL tree in context among its alternatives, which supports the comparison and trade-off subtopics directly and helps you see that "balanced" is a family of designs with different costs, not a single answer.
A performance comparison between binary search trees and hash tables. Expect a discussion of average-case versus worst-case lookup cost, and of the capabilities a hash table gives up, such as ordered traversal and range queries, in exchange for its speed.
Hash tables are the main competitor whenever an application is lookup-intensive, so this video sharpens the question of when an AVL tree is actually the right choice and when you should prefer an alternative.
Together these videos carry the module's complexity and trade-off outcomes. The AVL analysis video supplies the worst-case O(log n) argument that explains how the balance invariant prevents the O(n) degradation of an unbalanced BST, supporting MO1 and giving the complexity half of MO5. The comparison video extends that reasoning across red-black, splay, and heap structures, and the BST-versus-hash-table video adds the non-tree alternative, so that between them you have the evidence needed to justify selecting one structure over another for a given scenario as MO5 requires. These videos deliberately address performance and selection rather than the mechanics of rotations, heapify, or trie traversal covered in MO2 through MO4, which are developed elsewhere in the module.
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.
A heap is a complete binary tree that satisfies an ordering rule between every parent and its children: in a max-heap each parent is greater than or equal to its children, and in a min-heap each parent is less than or equal to its children. Notice what the heap property does NOT guarantee — there is no left-to-right ordering as in a binary search tree, so searching for an arbitrary value is still O(n). What you do get, cheaply and reliably, is constant-time access to the single most extreme element at the root, plus O(log n) insertion and removal. Because the tree is always complete, a heap needs no pointers at all: it can be packed into an array where the children of index i live at 2i+1 and 2i+2, and the parent at (i-1)/2.
That combination is exactly what a priority queue needs. A priority queue serves elements by priority rather than arrival order, and it underpins job schedulers, event simulation, Huffman coding, and the frontier in Dijkstra's and A* search algorithms — structures you will meet again later in this course and in algorithms courses. The two core maintenance routines are bubble-up (sift-up), used after appending a new element at the end of the array, and bubble-down (sift-down), used after moving the last element to the root when the root is extracted. Building a heap from an unordered array with heapify applies sift-down from the last internal node backwards, which runs in O(n) rather than the O(n log n) you might expect from n separate insertions.
As you watch, keep a pencil moving. Draw the tree and the array side by side, and after every swap check that both views still agree. Pay attention to when the speaker compares against a parent versus against children, how far a sifted element can travel (at most the height of the tree, hence O(log n)), and how the same two routines get reused for insertion, removal, heapify, and heapsort. Also note which videos use 0-based versus 1-based indexing, since the parent and child formulas change slightly between the two conventions.
An introductory lecture on heap trees that, based on its title and description, defines what a heap is and walks through examples of both max-heaps and min-heaps. Expect coverage of the complete binary tree requirement and the parent-child ordering property that distinguishes a heap from other binary trees, illustrated with worked examples rather than code.
This is the natural starting point for the first two subtopics — heap structure and the min-heap versus max-heap distinction — and Gate Smashers is a widely used exam-prep channel known for slow, example-driven board explanations that suit students seeing heaps for the first time.
The follow-up lecture in the same series, focused on inserting elements into a heap and building max-heaps and min-heaps from a sequence of values. The title also promises discussion of time complexities, so expect the per-insertion O(log n) cost and the overall cost of constructing a heap by repeated insertion to be addressed.
It targets the insertion and bubble-up subtopic directly and gives you repeated traced examples, which is precisely the skill of stepping through comparisons and swaps that you will be asked to demonstrate.
A longer, more technical treatment that covers heaps together with heapsort and priority queues, with source code linked in the description. Expect the array-based representation, the sift-up and sift-down routines, extraction of the root, and how a heap is used to implement a priority queue and to sort in place.
Inside code works at an implementation level, which fills in the removal, heapify, and priority-queue subtopics that the introductory lectures touch on more lightly, and connects the structure to a concrete application you can run and modify.
Together these videos build the array-based heap skill set targeted by MO3: the first establishes the complete-binary-tree and ordering properties, the second drills insertion with bubble-up, and the third completes the picture with root removal, sift-down, heapify, and the priority queue interface so you can trace each operation and compute parent and child indices confidently. The structural emphasis also supports MO1, since heaps keep their shape complete by construction and therefore never degrade the way an unbalanced BST does, and the recurring discussion of time complexities feeds MO5, where you will weigh a heap's O(1) access to the extremum and O(log n) updates against the full ordered traversal and search capability that an AVL tree offers.
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.
A binary heap is a complete binary tree that satisfies the heap property: in a min-heap every parent is no larger than its children, and in a max-heap every parent is no smaller. Because the tree is complete, we can store it in a plain array and compute relationships arithmetically — for a node at index i (0-based), its children sit at 2i+1 and 2i+2 and its parent at floor((i-1)/2). This array trick is what makes heaps fast and memory-efficient, and it is the reason heaps are the standard implementation behind priority queues.
The operations you need to master are few but must be traced carefully. Insert places a new element at the end of the array and sifts it up while it violates the heap property; extract-min or extract-max removes the root, moves the last element into the root slot, and sifts down; heapify restores the property at a subtree, and repeated heapify from the middle of the array builds a heap from unordered data. Insert and extract run in O(log n), peeking at the root is O(1), and building a heap bottom-up is O(n).
As you watch, keep two questions in mind. First, at every swap, what are the index computations — which child is chosen for comparison, and why? Second, how does a heap compare to alternatives such as a sorted array, an unsorted array, or a balanced BST: a heap gives you cheap access to the extreme element but does not support fast arbitrary search or ordered traversal, which is exactly the trade-off that decides when to use one.
A compact walkthrough of the core heap methods — building a heap and the insert and extract routines that keep the heap property intact — presented step by step with accompanying Python code linked in the description. Expect to see the sift-up and sift-down movement of elements illustrated on a concrete example.
Michael Sambol's data structures series is known for short, precise animations that match textbook algorithms, and this one directly targets the insert, extract, and heapify subtopics with runnable code you can read afterward.
A longer, example-driven lecture that explains the heapify method and then uses it to drive heap sort, working through a full example by hand. Along the way it covers how elements are arranged and reorganized as the largest or smallest element is repeatedly removed from the root.
The slower pace and worked example are useful for practicing the trace-by-hand skill, and seeing heapify applied to sorting reinforces why building a heap and repeatedly extracting the root are the key cost drivers in heap performance.
Together these videos target MO3 most directly: both walk through insert, extract, and heapify on concrete examples so you can practice tracing operations and the parent/child index arithmetic of the array representation. The emphasis on sift-up and sift-down paths bounded by the height of a complete tree also supports MO1 and MO5, giving you the O(log n) and O(n) results you will need in order to argue when a heap is preferable to an AVL tree, a sorted array, or a trie for a priority-based task.
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.
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.
So far in this module you have studied AVL trees, heaps, and tries one at a time, learning how each is built and how its operations work. This topic shifts the question from "how does it work?" to "when should I use it?" Each of these structures buys a particular guarantee at a particular cost: AVL trees pay for rotations and extra height bookkeeping in exchange for guaranteed O(log n) search on ordered data; heaps give up full ordering and fast arbitrary search in exchange for O(1) access to the minimum or maximum; tries trade significant memory for lookups whose cost depends on key length rather than the number of stored keys.
This matters because real engineering decisions are rarely about which structure is "best" in the abstract. They are about matching a structure's strengths to the operations your problem performs most often. A scheduler that repeatedly asks for the next highest-priority task, an index that must support ordered range queries, and an autocomplete box that resolves prefixes are three different problems with three different right answers. Being able to justify that choice — with complexity bounds and practical considerations like memory overhead and cache behavior — is the skill this topic develops.
As you watch the videos below, keep a comparison table in front of you with rows for AVL trees, heaps, and tries and columns for search, insert, delete, min/max access, space, and typical use cases. Note where the videos confirm what you already know, and pay attention to where real systems actually deploy these structures. Also watch for the common pitfalls: assuming a heap can search efficiently, assuming a balanced BST is always worth its rotation cost, and underestimating the memory footprint of a trie over a large alphabet.
This Geekific video places several tree structures side by side — plain binary search trees, AVL trees, red-black trees, splay trees, and heaps — and uses visualizations to show how their shapes and behaviors differ. Based on its title and framing, it should highlight why an unbalanced BST degrades, what balancing schemes do about it, and how a heap's ordering property differs from a search tree's.
This is the most directly on-topic video for the comparison itself, covering AVL trees and heaps in the same frame so you can see the structural contrast rather than studying them in isolation. Geekific's visual, example-driven style suits the "performance characteristics at a glance" and "decision framework" subtopics.
ByteByteGo surveys ten data structures that appear in everyday software systems, explaining for each one what problem it solves and where it shows up in practice. Expect heaps and tries to appear alongside hash tables, lists, and trees, each tied to a concrete application such as priority scheduling or autocomplete and spell checking.
It supplies the real-world use-case grounding that the decision framework depends on, connecting abstract complexity bounds to the kinds of problems each structure was designed for. ByteByteGo is a well-regarded systems-oriented channel and keeps the explanations short and application-focused.
This short ByteByteGo video looks at the data structures underlying modern database systems, covering the structures used for indexing, ordered access, and fast lookup. Given the topic, it is likely to discuss balanced search trees and B-trees for indexes and to touch on specialized structures chosen for particular query patterns.
It shows why balance guarantees matter at scale, which reinforces the "AVL trees: when balance is the priority" subtopic and the trade-off between in-memory tree balancing and disk-oriented alternatives. It also models the professional habit of justifying a structure choice by the workload it must serve.
Together these videos target the evaluative end of the module. The Geekific comparison reinforces MO1 by contrasting a degenerate BST with balanced and heap-ordered alternatives, and it reviews the structural invariants behind the rotation and heap mechanics you practice in MO2 and MO3. The two ByteByteGo videos primarily serve MO5: they connect heaps, tries, and balanced trees to the workloads they are actually deployed against, giving you concrete scenarios to reason about when justifying a selection, and the everyday-structures survey offers application context for the prefix operations you trace in MO4. None of the videos replaces hands-on tracing practice; use them to build the comparative judgment layer on top of the mechanics.
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.