Trees and Priority Queues

reading · we frame, you read MIT or the canonical taught · we author, no canonical fits ↺ spirals back to earlier lessons

Course locked

Complete Linear Data Structures first.

This course unlocks once you've finished its prerequisite. Open prerequisite →

Prerequisites

Linear Data Structures not yet

Complete prerequisites first to enroll.

reading · 35 min + ~280 min canonical

Binary Trees and the Recursive Mind-Shift

Until now, the data structures you've built have been flat. Arrays are a row of values; linked lists are a chain. You walk them with a loop. Trees break that pattern in a specific…

primary UC Berkeley CS61B — Trees, BSTs, Heaps sections

preview →

reading · 30 min + ~280 min canonical L1

Binary Search Trees: The Order Invariant That Earns You log n

You ended the last lesson with an inorder traversal that printed 1, 3, 4, 5, 8, 9, 11 — sorted. That wasn't an accident. The tree was a Binary Search Tree, a binary tree where eve…

primary UC Berkeley CS61B — Trees, BSTs, Heaps sections

after L1 locked

reading · 35 min + ~280 min canonical L1

Balanced BSTs: AVL, Red-Black, and the Self-Correcting Tree

You ended the last lesson with the BST that degenerated into a linked list when given sorted input. The fix isn't a different data structure — it's the same BST with one more inva…

primary UC Berkeley CS61B — Trees, BSTs, Heaps sections

after L2 locked

reading · 35 min + ~280 min canonical L1

B-Trees: Why Your Database Index Is Shaped Like This

A binary search tree gives you O(log₂ n) operations. For n = 1 billion that's ~30 comparisons. Sounds fast. Now consider where the tree lives: if it's on a spinning disk (or even …

primary UC Berkeley CS61B — Trees, BSTs, Heaps sections

after L3 locked

reading · 30 min + ~280 min canonical L1

Heaps, Priority Queues, and Heap Sort: The Array-Backed Tree

A regular queue is fair: oldest in, oldest out. But almost every system you've ever used violates that fairness for a reason — the OS's process scheduler runs urgent tasks before …

primary UC Berkeley CS61B — Trees, BSTs, Heaps sections

after L4 locked

exercise reading · 15 min L1

Exercises: Easy (Warm-up)

- [ ] Invert Binary Tree (#226) — NC/LC — Recursive swap of left/right children - [ ] Maximum Depth of Binary Tree (#104) — NC/LC — Recursive or BFS depth calculation - [ ] Diamet…

after L5 locked

exercise reading · 30 min L1

Exercises: Medium (Core)

- [ ] Binary Tree Level Order Traversal (#102) — NC/LC — BFS with level tracking - [ ] Validate Binary Search Tree (#98) — NC/LC — Inorder traversal or min/max range - [ ] Kth Sma…

after L6 locked

exercise reading · 45 min L1

Exercises: Hard (Stretch)

- [ ] Binary Tree Maximum Path Sum (#124) — NC/LC — DFS tracking max path through each node - [ ] Serialize and Deserialize Binary Tree (#297) — NC/LC — Preorder with null markers…

after L7 locked

exercise reading · 60 min L1

Mini-Project

- [ ] Build a Huffman encoder/decoder in Ruby — construct the Huffman tree from character frequencies using a priority queue, generate prefix codes, compress and decompress a text…

after L8 locked

L10

project reading · 300 min L1

Project: Priority Queue Task Scheduler

Build a min-heap-based priority queue in Ruby. Use it to implement a task scheduler where tasks have priorities and deadlines. Support addtask, nexttask, peek, updatepriority. Wri…

after L9 locked

L11

project reading · 360 min L1

Project: BST Visualizer

Implement a BST and AVL tree in Ruby. After each insertion or deletion, print the tree structure as ASCII art (showing the tree shape with node values). Demonstrate how the AVL tr…

after L10 locked

L12

assessment reading · 70 min L1

Self-Assessment: Trees and Priority Queues

- [ ] What are the four tree traversals (inorder, preorder, postorder, level-order)? When would you use each? - [ ] What is a Binary Search Tree? What is its worst-case time compl…

after L11 locked

12 lessons. Read in order; spiral back when you need to. By the end you'll have used the core ideas twice — once on the abstract, once on something you'll meet at work next week.