Speaker note: Today a node gets to point at more than one other node. That single change — one pointer becomes two — is the entire jump from "list" to "tree", and it builds the heap, priority queues, and Huffman coding, all in one sitting.
Speaker note: Eighteen short animations carry the whole lecture; each appears once, exactly where its idea is introduced, and several get a second look at their trickiest edge case.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: A tree node is a linked-list node with one extra pointer field — that is genuinely the whole new idea.
Speaker note: Nothing about memory is new this week — only new shapes built from the exact same pointer and stack/queue ideas.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 builds the vocabulary every later section leans on — root, parent, child, leaf, depth, height — on a general tree where a node may have any number of children.
Speaker note: Ask: is this shape a stack, a queue, or something new? It branches — that is the whole new idea today.
Speaker note: Cayley was not thinking about computers at all — he was counting hydrocarbon isomers, whose branching structure is literally a tree.
Speaker note: Ask why "root" sits at the top — it is a convention, not a law of nature, but it is completely universal in this field.
Speaker note: Every one of these is pointed at, one at a time, in the animation right after this table.
Speaker note: n-1 edges is worth pausing on: every node except the root has exactly one edge, to its own parent.
Speaker note: Depth counts down from the root; height counts down from a node to its deepest leaf — the direction of counting is what people confuse.
Speaker note: Normal example: an 11-node bushy tree. Watch each term light up on the same real tree, one at a time.
Speaker note: A star tests "degree" hardest: one node with degree 10, ten leaves each with degree 0, and a tree of height only 1.
Speaker note: Compare this to Week 2's linked-list node: same idea, but children is now an array, since a general tree node may have many children, not just one "next".
Speaker note: A leaf's height is the base case, 0; every other node is 1 plus its tallest child — pure recursion, no queue needed.
Speaker note: Depth needs the parent's answer first, so it walks top-down with a queue — the mirror image of height's bottom-up recursion.
Speaker note: Shape will start to matter a lot once we look at recursion *depth* rather than total work, later this week.
Speaker note: The binary restriction starts in the very next section, and it is a choice we make for its tricks, not a law of nature.
Speaker note: Let the class answer both parts before the next slide.
Speaker note: Depth always adds exactly one per level down from the root — no shortcuts, no exceptions.
Speaker note: One restriction — at most two children, called left and right — unlocks the heap, Huffman coding, and next semester's search trees.
Speaker note: The payoff is arithmetic tricks on array indices, which section 4 introduces — impossible with unlimited children.
Speaker note: Every program for the rest of this week builds on exactly this struct — one more pointer than a linked-list node.
Speaker note: These are five independent yes/no questions — a tree can be complete without being full, and vice versa.
Speaker note: Normal example: 12 nodes, complete but not perfect. The animation asks all five yes/no questions on the same tree.
Speaker note: A degenerate tree fails full, complete, and perfect all at once, and its height is n-1 — as bad as a plain linked list.
Speaker note: These two formulas come back constantly — the heap in section 5 depends on both.
Speaker note: Balance is the whole reason binary search trees, next semester, are worth building carefully rather than by accident.
Speaker note: This walks level by level with a queue, deliberately enqueuing NULL placeholders so a real node right after a gap gets caught.
Speaker note: One sentinel value, -1, carries "already unbalanced" up the recursion so we never re-walk the same subtree twice.
Speaker note: h is the height, which is why a degenerate tree's O(n) stack space is the worst case worth worrying about.
Speaker note: The one-pass check_balance above exists specifically to avoid that last, very common trap.
Speaker note: Use both formulas from two slides back.
Speaker note: Every perfect tree's leaf count is exactly half its total nodes, rounded up — a nice sanity check.
Speaker note: A tree has no one natural order — a node has two children, so there is a real choice about which to visit first and when to visit the node itself.
Speaker note: All five programs below share the same 10-node balanced tree [50,30,70,20,40,60,80,10,-,-,45,55], so only the visiting order ever changes.
Speaker note: Reading the sequence back in, the very first value read is always the root of whatever subtree comes next.
Speaker note: Watch the highlighted call path trace the route from the root down to whichever call is currently active.
Speaker note: With only left children, preorder visits in exactly the order the chain was built — visit, then the one child, every time.
Speaker note: Visit first, then recurse left, then right — the base case, node == NULL, must come first or this crashes on an empty subtree.
Speaker note: On these demonstration trees, which are not built by BST rules, inorder still runs left-before-self-before-right; it just does not happen to sort.
Speaker note: On the normal tree, [50,30,70,...], inorder happens to come out perfectly sorted: 10 20 30 40 45 50 55 60 70 80.
Speaker note: With only right children there is no left subtree to visit first, so inorder comes out in the exact chained order — compare this to the left-skewed case, which comes out reversed.
Speaker note: Identical shape to preorder — only the position of the "visit" line moves, from first to the middle.
Speaker note: Free a node's children before the node itself, or you would need the node's own pointers again after they are already gone.
Speaker note: Compare this run's very first and very last printed values with preorder's — root last here, root first there.
Speaker note: With no left subtree, postorder still saves "visit self" for last, so the whole right chain comes out in reverse chained order.
Speaker note: Same three lines as always, just moved to the end — visit, left, right becomes left, right, visit.
Speaker note: Only the order of "visit, left, right" changes between the three; the total work never does.
Speaker note: All three "visit every node", so a wrong choice still runs — the bug only shows up once the order itself matters.
Speaker note: Think about which value must be read first.
Speaker note: This is exactly the "rebuild from scratch" property mentioned at the start of the preorder slides.
Speaker note: Push the whole left spine; when you cannot go left any further, pop, visit, then walk into the right subtree and repeat.
Speaker note: Watch the stack grow as the left spine is pushed, then shrink one pop at a time as each node is visited.
Speaker note: All 10 nodes get pushed before a single one is popped — the stack depth equals the whole chain's length.
Speaker note: The exact array-based stack from Week 3 — only the element type changed, from int to Node *.
Speaker note: Push the whole left spine, pop and visit, then step right and repeat — both halves of the outer while matter.
Speaker note: A pathologically deep tree can crash a recursive call stack; our own array-based stack just runs out of room more gracefully.
Speaker note: Both halves of that loop condition matter — drop the first and you stop too early, drop the second and you loop forever.
Speaker note: Think about which nodes the stack actually holds at any moment.
Speaker note: Depths 0 through h, inclusive — that is h+1 nodes, never more.
Speaker note: The first node enqueued, the root, must also be the first processed — that is exactly FIFO, so a stack would give the wrong order.
Speaker note: Watch each depth finish completely — 50, then 30 and 70, then all four grandchildren — before the next depth starts.
Speaker note: Every node here has only one child, so there is never more than one node "at" any depth — the queue never grows past size 1.
Speaker note: The exact circular queue from Week 3 — rear starts at -1 so the very first enqueue correctly lands on index 0.
Speaker note: Unlike section 2's completeness check, this loop never enqueues NULL — mixing the two conventions up is a classic source of bugs.
Speaker note: Depth-first traversals trade width for depth; level order trades depth for width — neither is free.
Speaker note: The code still compiles and runs either way; only the actual visiting order reveals the bug.
Speaker note: Think about whether a level-order sequence alone tells you which node is whose child.
Speaker note: A preorder-plus-inorder pair together does determine one specific tree; a single level-order sequence does not.
Speaker note: For a complete tree specifically, arithmetic on an index replaces every pointer — no malloc, no left/right fields at all.
Speaker note: Yes — and it is exactly the representation the binary heap in section 5 is built on.
Speaker note: Three formulas are the entire representation; everything else is pure arithmetic on one plain array.
Speaker note: Normal example: 12 nodes, complete, no gaps at all — every formula lands exactly where the picture says it should.
Speaker note: Indices 9 and 10 are empty but index 11 is filled — one real node after a gap is enough to break completeness entirely.
Speaker note: Three one-line formulas, then one loop: any empty slot before the last real one means the array is not complete.
Speaker note: O(1) child/parent access is the entire point of the array representation — it is exactly what the heap needs next.
Speaker note: The formulas still compute *some* index either way; on a non-complete tree, that index may simply be meaningless.
Speaker note: Apply all three formulas from a few slides back.
Speaker note: Same three formulas, every single time, regardless of how large the tree is.
Speaker note: A binary heap is a complete tree, from section 4, with one extra rule: every parent beats both its children.
Speaker note: Sorting on every arrival costs O(n log n) per arrival — far too slow for something this frequent.
Speaker note: Both papers appeared the very same year — the heap and heap sort were never really separate ideas.
Speaker note: This is the single most common misconception about heaps: a heap is not a sorted array, only a partially ordered one.
Speaker note: Four operations, and the next four subsections build exactly these four, in this order.
Speaker note: Stop the moment the property holds, or when the value reaches the root — whichever comes first.
Speaker note: Normal example: a min-heap, 10 values inserted one by one: 15, 7, 22, 3, 18, 9, 30, 1, 25, 12.
Speaker note: 12 ascending values into a min-heap: every single insert already satisfies the heap property, so not one swap ever happens.
Speaker note: better() hides min-heap vs max-heap behind one function, so the sift-up loop itself never needs to change.
Speaker note: Height, not size, decides insert's cost — exactly the "why balance matters" idea from section 2, put to work.
Speaker note: Shrink size by one first, then sift — the moved element usually does not belong at the root at all.
Speaker note: Normal example: a min-heap, 12 values, 3 extractions — watch the last element parachute into the root, then sink back down.
Speaker note: Extracting all 10 values, one at a time, produces them in fully sorted order — that is not a coincidence, it is how heap sort works.
Speaker note: Compare with both children, not just the left one — comparing only one side can leave the property broken on the other.
Speaker note: Insert climbs at most log n levels; extract sinks at most log n levels — heights, again, decide everything.
Speaker note: An empty-heap extract reads heap[-1]-adjacent memory silently — a dangerous bug, not a clean crash.
Speaker note: This is a genuinely surprising result — building looks like it should cost the same as n inserts, but it does not.
Speaker note: Normal example: a max-heap, 10 values in arbitrary order — watch how few of the n/2 leaves ever move at all.
Speaker note: Every sift-down call finds target == i immediately and does nothing — build_heap does exactly as much work as the input needs, no more.
Speaker note: sift_down here is the exact same loop as extract's sift-down; the only new idea is which nodes to call it on, and in which order.
Speaker note: This is the one genuinely surprising complexity result of the whole week — worth sitting with for a moment.
Speaker note: The loop must run backward, from the last internal node to the root, so every node's subtrees are already valid by the time it is sifted.
Speaker note: Think about where in the tree each call to sift-down starts from.
Speaker note: Same function, sift_down, called in two very different patterns, with two very different total costs.
Speaker note: Once build_heap and extract both exist, sorting is almost free — this section just wires the two together.
Speaker note: Normal example: ascending sort with a max-heap, 10 values — watch the sorted region grow from the array's tail backward.
Speaker note: Unlike build-heap, heap sort is not adaptive — an already-sorted input still costs the full O(n log n), swap for swap.
Speaker note: The very same build_heap loop from before, then n-1 rounds of swap-and-sift, each on a shrinking region.
Speaker note: Same asymptotic class as merge sort or quicksort's average case, but with no extra memory needed.
Speaker note: If a stable sort is required, heap sort is simply the wrong tool, regardless of its good time complexity.
Speaker note: A queue serves whoever arrived first; a priority queue serves whoever matters most, arrival order be damned.
Speaker note: Almost nothing new here — the heap from section 5 is by far the most common way to implement one.
Speaker note: update_key is the one genuinely new operation, and it is the whole reason each item needs a permanent id.
Speaker note: Each item needs a permanent id, stable no matter where it moves inside the array, or update_key cannot find it again.
Speaker note: Normal example: min-priority, 10 inserts, a peek, 2 extracts, and one update-key — the same 15,7,22,3,18,... values as section 5's heap-insert.
Speaker note: The caller checks size > 0, not the heap operations themselves — this scenario shows that check catching underflow safely.
Speaker note: Every item now carries a permanent id alongside its key — the id never moves, even when the item's array slot does.
Speaker note: find_by_id is a linear scan here — a real system adds a hash table from id to index to make this O(log n) too.
Speaker note: That extra bookkeeping is a classic space-for-time trade, worth it once thousands of items are in play.
Speaker note: Decrease-key needs sift-up; increase-key needs sift-down — using the wrong one leaves the heap silently broken.
Speaker note: Think about what "more urgent" means for the key's numeric value in a min-priority queue.
Speaker note: In a min-priority queue, smaller is always better — the same rule as section 5's min-heap.
Speaker note: Each variant below relaxes or changes one property of the plain binary heap, in exchange for a different advantage.
Speaker note: A larger D makes insert cheaper (fewer levels, one comparison each) but extract more expensive (up to D comparisons per level).
Speaker note: Normal example: D=3, a min-heap, 3 extractions from 12 values — watch each sift-down compare against up to 3 children at once.
Speaker note: All 10 values extracted, one at a time — again comes out fully sorted, exactly like the plain binary heap's drain case.
Speaker note: base = D*i+1 replaces the binary heap's 2*i+1 — every other line of extract stays exactly the same shape.
Speaker note: Popular for insert-heavy workloads like network event schedulers, where extract is comparatively rare.
Speaker note: 2*i+1 and 2*i+2 are just the D=2 special case of D*i+1+c — plug in the wrong D and the wrong array cell gets touched.
Speaker note: 13 = 0b1101 decomposes into orders 0, 2, and 3 — trees of size 1, 4, and 8, summing to 13.
Speaker note: This "three trees at once" case is exactly what the hard scenario in the animation is built to exercise.
Speaker note: Normal example: min, A has 7 elements (orders 0,1,2), B has 5 (orders 0,2) — watch the carries ripple upward.
Speaker note: A (order 3) union B (order 3): a single carry ripples through every order, just like adding 1000 + 1000 in binary.
Speaker note: link() makes the worse root a new leftmost child of the better root — O(1), just a handful of pointer updates.
Speaker note: A plain binary heap's insert is also O(log n), but for a completely different reason: sift-up, not linking.
Speaker note: insert is not a separate algorithm to memorize — it is exactly union_heaps with a single-element second heap.
Speaker note: insert is merge with one new node; extract is merge of the root's two children, after the root itself is removed.
Speaker note: The tree may be wildly unbalanced overall — only the right spine is guaranteed short, and merge only ever walks that spine.
Speaker note: Normal example: min, A has 5 elements, B has 6 — watch merge splice down both right spines, then fix npls on the way back up.
Speaker note: A is empty, merging with an 11-element B — merge's two base cases (t1 == NULL, t2 == NULL) handle this immediately.
Speaker note: The better root always wins and absorbs the other tree into its own right side, then the swap restores the leftist property.
Speaker note: Only the right spine's length matters, and the leftist property guarantees it is always short.
Speaker note: Skip that swap, and the whole O(log n) short-right-spine guarantee quietly stops holding.
Speaker note: Think about which structure has no fast way to merge two whole heaps at all.
Speaker note: A plain array heap's only way to merge is re-inserting every element of one heap into the other, one at a time.
Speaker note: The payoff for everything this week has built: a heap of trees, and nothing else, produces an optimal compressed code.
Speaker note: The catch: mixed-length codes in one bitstream could be ambiguous to decode, unless built with one very specific property.
Speaker note: Huffman's professor offered the class a choice: take the final exam, or find a provably optimal prefix code — Huffman found one.
Speaker note: Rare symbols merge early, staying near the bottom; common symbols merge late, staying near the top — exactly what gives them short codes.
Speaker note: Normal example: 10 symbols with English-letter-like frequencies — watch the two smallest roots merge, again and again.
Speaker note: Just 2 symbols: one merge, one root, done — the smallest input for which "build a tree" even means anything.
Speaker note: heap_pop/heap_push are exactly section 5's min-heap extract/insert, ordering Node pointers instead of plain ints.
Speaker note: Every symbol is exactly one leaf, and a leaf has no children — so no code can ever be a prefix of another.
Speaker note: Normal example: "ABRACADABRA", 11 characters — 88 plain-ASCII bits shrink to 23, because A alone is 5 of the 11 characters.
Speaker note: Only 2 symbols left, so 1 bit per character is the best possible — 10 bits instead of 80, no matter how skewed the frequencies are.
Speaker note: Only leaves ever record a code; every internal node just extends the path with a 0 (left) or a 1 (right).
Speaker note: One tree step per bit; the moment a leaf is reached, emit its character and restart the walk from the root.
Speaker note: L is the text's length in characters; B is the encoded message's length in bits.
Speaker note: The decoder always needs either the tree or the frequency table shipped alongside the encoded bits.
Speaker note: Think about what a leaf's position in the tree does, and does not, allow.
Speaker note: This "prefix-free" property is exactly what makes single-pass, unambiguous decoding possible.
Speaker note: Five ways to visit the same tree, and one way to store a complete one without a single pointer.
Speaker note: Every one of these five rows is built from the same two moves: sift-up and sift-down.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These mirror the self-check quiz at the end of the written notes, one question per slide, with a shorter set here.
Speaker note: Ask, wait, then advance.
Speaker note: The same formula from section 2, just with h = 4.
Speaker note: Apply the formula from section 4.
Speaker note: Same formula, every time, regardless of the tree's size.
Speaker note: Recall the height-weighted sum from section 5.5.
Speaker note: The few costly sifts near the top are heavily outnumbered by the many cheap ones near the bottom.
Speaker note: Recall what changes on almost every operation.
Speaker note: update_key needs some way to find "this specific item" that does not depend on where it currently sits.
Speaker note: update_key was built for exactly this: "repeatedly extract the closest item, then maybe lower some other item's priority."
Speaker note: These are the same references listed at the end of the week's written notes.
Speaker note: The historical references — Huffman, Williams, Floyd, Vuillemin, Cayley — are what today's "short history" slides drew on.