Today, we continue our discussion of binary trees and binary search trees. We encounter some light puzzles, a few applications, and some binary tree code.
- Readings: Text 16.2 - 16.4
- Lecture quiz on Canvas
We continued our discussion of BST's today.
We started (timestamp 3:17) with a refresher of our pre-order, post-order, and in-order traversal algorithms, as well as (timestamp 6:40) a small challenge problem where we identified which among an unlabeled set of traversals for some unknown tree must have been pre-order, which was post-order, and which was in-order.
From there, we talked (timestamp 11:30) about using BSTs to solve a real-world problem and the concomitant risk of our BST devolving into a linked list and giving us O(n) runtimes for our insertion, search, and deletion operations as a result. I briefly talked (timestamp 16:30) about balanced binary search trees (such as AVL trees, red-black trees, and 2-4 trees), which keep a BST nice and balanced and bushy, thereby guaranteeing worst-case O(log n) runtimes for those operations.
We then paused (timestamp 25:07) to see a few examples of places where trees are used to solve real-world problems. As part of that, I mentioned that balanced BSTs actually drive the implementation of our Stanford Set and Map classes!
I then (timestamp 29:34) talked about how we could implement a level-order traversal using a queue. From there, we started coding up binary trees (timestamp 32:18) starting with a Node struct and a manually-constructed BST, our recursive (timestamp 34:45) pre-, post-, and in-order traversal algorithms, and our (timestamp 41:08) queue-based level-order traversal.
We concluded (timestamp 47:12) with a recursive bstInsert() function. We passed our root pointer to that function by reference and talked about our motivation for doing that, along with a few diagrams showing what was going on in memory.
All of today's code is posted toward the top of the notes for Lecture 23 (Binary Trees: Loose Ends), where we implemented our bstDelete() function and put all the finishing touches on our implementation of BSTs.