Week 5: Hash Tables and Binary Search Trees

DSAN 5500: Data Structures, Objects, and Algorithms in Python

Jeff Jacobs

jj1088@georgetown.edu

Thursday, February 5, 2026

Schedule

Today’s Planned Schedule:

	Start	End	Topic
Lecture	6:30pm	7:00pm	Inductive Thinking →
	7:00pm	7:30pm	`LinkedList`: Our Core Linear Data Structure →
	7:30pm	8:00pm	`BinarySearchTree` aka `FancyLinkedList` →
Break!	8:00pm	8:10pm
	8:10pm	9:00pm	`HashTable`: The Final Missing Piece! →

Induction: The Core “Way of Thinking” for Algorithm Design…

Jeff has messed up the “intuitive” explanation for Gauss’ Sum on the board every semester since 2010
Most years this is a problem…
But this year it’s an opportunity to teach induction!

The Intuition

(What I should have done on the board)

$\Rightarrow \displaystyle\sum_{i=1}^{6} = \frac{6(6+1)}{2}$ …but can we infer $\displaystyle \sum_{i=1}^{n} = \frac{n(n+1)}{2}$? Not in general!
(When you do it’s called “Engineer’s induction”… see next slide)
(Double no in this case since we assumed $n$ even!)
But, with only slight increase in complicated-ness, can prove it by induction, which is used in… 95% of algorithm/data structures proofs! (We’ll see why)

What’s Wrong With Engineers’ Induction?

What if I told you, I have a simple polynomial that we can use to infinitely generate prime numbers! $\boxed{f(n) = n^2 + n + 41}$… Let’s try it!

$n$	$f(n)$	Prime?
0	41	✅
1	43	✅
2	47	✅
3	53	✅
$\vdots$	$\vdots$	✅

$n$	$f(n)$	Prime?
38	1523	✅
I can stop checking now right?
39	1601	✅
Surely I’ve checked enough terms?
40	1681	❌ $1681 = 41 \times 41$ 💀
Maybe that’s the only exception?
41	1763	❌ $1763 = 41 \times 43$ 💀
Maybe we can get composites* $n > 41$?*
42	1847	✅ 💀💀💀 USELESS!

(Non-Engineers’) Induction!

Goal: Prove $p(n)$ (“predicate”, evaluates to T/F for given $n \in \mathbb{Z}^{\geq 0}$)
The core is literally just: If I know
- Base Case: [$p$ is true for $n = n_0$]
- Inductive Step: [$p$ is true for $n$] $\implies$ [$p$ is true for $n + 1$]
Then I can conclude $p(n)$ true for all $n \geq 1$!

Gauss’ Summation Formula: $p(n) = \left[ \sum_{i=0}^{n}i = \frac{n(n+1)}{2} \right]$
Base Case: $n_0 = 1$:

\[ \sum_{i=0}^{1} = 0 + 1 \overset{?}{=} \frac{(1)(1+1)}{2} \iff 1 \overset{?}{=} \frac{2}{2} \iff 1 \overset{✅}{=} 1 \]

Inductive Step: Can I Infer $n + 1$ From $n$?

Assume $p(n)$, that is, $\displaystyle\sum_{i=0}^{n}i = \frac{n(n+1)}{2}$.
Goal: Derive $p(n + 1)$, that is, $\displaystyle\sum_{i=0}^{n+1}i = \frac{(n+1)(n+2)}{2}$…
Start with LHS term, $\sum_{i=0}^{n+1}i$:

\[ \begin{align*} \boxed{\sum_{i=0}^{n+1}i} &= \underbrace{0 + 1 + 2 + \cdots + n}_{\sum_{i=0}^{n}i} + (n+1) = \underbrace{\sum_{i=0}^{n}i}_{\mathclap{\text{LHS of }p(n)}} + (n+1) \\ &= \frac{n(n+1)}{2} + (n + 1) = \frac{n^2 + n}{2} + \frac{2(n+1)}{2} \\ &= \frac{n^2 + 3n + 2}{2} = \boxed{\frac{(n+1)(n+2)}{2}} \; ~ ✅ \end{align*} \]

(Algorithmic/Data-Structural Proofs Almost Always Inductive!)

“Direct” proof, in this case, is doable but requires stuff like…
Break into [Case 1: $n$ even] and [Case 2: $n$ odd]
In case 2

\[ \sum_{i=0}^{n}i = 1 + 2 + \cdots + \left( \left\lceil \frac{n}{2} \right\rceil - 1\right) + \left\lceil \frac{n}{2} \right\rceil + \left( \left\lceil \frac{n}{2} \right\rceil + 1\right) + \cdots + (n-1) + n \]
Need to show (…with induction?) $\left\lceil \frac{n}{2} \right\rceil = \begin{cases}\frac{n}{2} &\text{if }n\text{ even} \\ \frac{n+1}{2} &\text{if }n\text{ odd}\end{cases}$
And so on…

Core Data Structure: `LinkedList`

Looking Under the Hood of a Data Structure

Last week we saw the math for why we can “abstract away from” the details of how a particular language works
We want to understand these structures independently of the specifics of their implementation in Python (for now)
So, let’s construct our own simplified versions of the basic structures, and use these simplified versions to get a sense for their efficiency
- (The “true” Python versions may be hyper-optimized but, as we’ll see, there are fundamental constraints on runtime, assuming $P \neq NP$)

Tuples

Code

class MyTuple:
  def __init__(self, thing1, thing2):
    self.thing1 = thing1
    self.thing2 = thing2

  def __repr__(self):
    return f"({self.thing1}, {self.thing2})"

  def __str__(self):
    return self.__repr__()

t1 = MyTuple('a','b')
t2 = MyTuple(111, 222)
print(t1)
print(t2)

(a, b)
(111, 222)

Lists

The list itself just points to a root item:

Code

class MyList:
  def __init__(self):
    self.root = None

  def append(self, new_item):
    if self.root is None:
      self.root = MyListItem(new_item)
    else:
      self.root.append(new_item)

  def __repr__(self):
    return self.root.__repr__()

An item has contents, pointer to next item:

Code

class MyListItem:
  def __init__(self, content):
    self.content = content
    self.next = None

  def append(self, new_item):
    if self.next is None:
      self.next = MyListItem(new_item)
    else:
      self.next.append(new_item)

  def __repr__(self):
    my_content = self.content
    return my_content if self.next is None else f"{my_content}, {self.next.__repr__()}"

Code

users = MyList()
users.append('Jeff')
users.append('Alma')
users.append('Bo')
print(users)

Jeff, Alma, Bo

So, How Many “Steps” Are Required…

To retrieve the first element in a MyTuple?
To retrieve the last element in a MyTuple?
To retrieve the first element in a MyList?
To retrieve the last element in a MyList?

How Many Steps?

With a MyTuple:

Code

t1.thing1

'a'

$\implies$ 1 step

Code

t1.thing2

'b'

$\implies$ 1 step

With a MyList:

Code

print(users.root.content)

Jeff

$\implies$ 1 step

Code

current_node = users.root
while current_node.next is not None:
  current_node = current_node.next
print(current_node.content)

Bo

$\implies$ (3 steps)

…But why 3? How many steps if the list contained 5 elements? $N$ elements?

Visualizing `LinkedList`s

Code

from hw2 import LinkedList, InventoryItem
ll = LinkedList()
item1 = InventoryItem('Mango', 50)
ll.append(item1)
item2 = InventoryItem('Pickle', 60)
ll.append(item2)
item3 = InventoryItem('Artichoke', 55)
ll.append(item3)
item5 = InventoryItem('Banana', 123)
ll.append(item5)
item6 = InventoryItem('Aardvark', 11)
ll.append(item6)
HTML(visualize_ll(ll))

Onwards and Upwards: Fancier Algorithms

LinkedList: Foundation for Most(?) Data Structures!

class LinkedList(BaseModel):
  root: LinkedListNode | None

class LinkedListNode(BaseModel):
  content: object
  next: LinkedListNode | None

class BinaryTree(BaseModel):
  root: BinaryTreeNode | None

class BinaryTreeNode(BaseModel):
  content: object
  left: BinaryTreeNode | None
  right: BinaryTreeNode | None

class QuadTree(BaseModel):
  root: QuadTreeNode | None

class QuadTreeNode:
  content: object
  nw: QuadTreeNode | None
  ne: QuadTreeNode | None
  sw: QuadTreeNode | None
  se: QuadTreeNode | None

Visualizing `BinarySearchTree`

Code

from hw2 import BinarySearchTree
bst = BinarySearchTree()
item1 = InventoryItem('Mango', 50)
bst.add(item1)
item2 = InventoryItem('Pickle', 60)
bst.add(item2)
item3 = InventoryItem('Artichoke', 55)
bst.add(item3)
item5 = InventoryItem('Banana', 123)
bst.add(item5)
item6 = InventoryItem('Aardvark', 11)
bst.add(item6)
HTML(visualize(bst))

So Then… Why Is This a Whole Class?

The core structures are identical, but we can optimize different goals (efficient insertion, sorting, retrieval, deletion, …) by changing the invariants maintained by the algorithms internal to our structure
Crucial Insertion-Sort invariant: $\textsf{Sorted}(1,i)$ true when we move to entry $i + 1$ (key)
Crucial HW2(!) invariant: $\textsf{Up-To-Date-Favorite}(1,i-1)$ true when entry $i + 1$ (next result in dataset) arrives
$\implies$ Efficiency of obtaining favorite style guaranteed to be constant-time, $\overline{O}(1)$!
Otherwise, would be $\overline{O}(n) > \overline{O}(1)$ (linear approach) or at best $\overline{O}(\log_2(n)) > \overline{O}(1)$ (divide-and-conquer)

Hash Tables

(Spoiler alert, so you know I’m not lying to you: this is a LinkedList with some additional structure!)
You just got hired as a cashier (Safeway cashiering alum myself 🫡)
The scanner is broken (spoiler #2: the scanner uses a hash table), so you start writing down items along with their prices, one-by-one, as items come in…

Our List of (Item, Price) Pairs

Code

price_list = []
price_list.append(('Banana', 10))
price_list.append(('Apple', 2))
price_list.append(('Four Loko', 5))
price_list

[('Banana', 10), ('Apple', 2), ('Four Loko', 5)]

As the list gets longer, it gets harder and harder to find where you wrote down a specific item and its price
As you now know, you could use linear search, $\overline{O}(n)$, or if you ensure alphabetical order (an invariant!), you could use binary, divide-and-conquer search, $\overline{O}(\log_2(n))$
We can do even better: $\overline{O}(1)$. First w/magic, but then math

Strange-At-First Technique for Algorithm Analysis: Oracles

What if we had a magical wizard who could just tell us where to find an item we were looking for?
Sounds like I’m joking or saying “what if we had a billion $ and infinite aura and we could fly and walk through walls”
And yet, through the magic of math and computer science, there are concrete hashing algorithms which ensure (in a mathematically-provable way!) “almost certain” $\overline{O}(1)$ lookup time

Mathematical Strategy of Oracles

We’ll use a concrete, simplified hash function to illustrate
Mathematically we’ll be able to get something like

\[ T(n) = \overline{O}(1 + \underbrace{\epsilon}_{\mathclap{\text{Collision rate}}} \cdot n) \]

Which tells us: if we had an oracle who could ensure near-0 collision rates, then $T(n) = \overline{O}(1)$.
And, by a beautiful division-of-labor, other computer scientists figure out the near-0 collision rates part, giving us

\[ p^{✅} = [T(n) = \overline{O}(1 + \epsilon n)], q^{✅} = [\epsilon \approx 0],\text{ so } p \wedge q \implies T(n) \overset{✅}{=} \overline{O}(1). \]

Back to the Price List

Our hash function: hash(item) = first letter of item

\[ h(\texttt{x}) = \texttt{x[0]} \]

h('Banana') = 'B', h('Monkey') = 'M'
With this function in hand, we can create a length-26 array, one slot for each letter in alphabet, then write down (item, price) pairs in whatever slot item hashes to

The Importance of Differentiating Operations: Insertion vs. Lookup

So far, we have $\overline{O}(1)$ insertion via hashing
We also get $\overline{O}(1)$ lookup!
When customer hands us an item (say, 'Banana'), we compute the hash (B), look in that slot, and obtain the price for bananas.
We also get $\overline{O}(1)$ updating (hash to find the old price, update it to have new price) and $\overline{O}(1)$ deletion (hash to find the slot containing the item, then erase it from that slot)

So What’s the Catch???

BLUEBERRIES show up to ruin our day (as usual 😞)
We hash, so far so good: h('Blueberries') = 'B'
But then we go to the B slot and see that (Bananas, 10) is already there!!! Wtf do we do here… don’t panic!
The answer? We open our HW2 from DSAN 5500 and remember that we have our lovely friend the LinkedList that we can use whenever and however we want!

Arrays vs. Linked Lists

Jeff is hiding something here… Why jump to LinkedList? Why not just… another length-26 array, for example?
For this we open up our Week 1 slides and remember the stack vs. heap distinction: we know how many letters in the alphabet, we don’t know how many items starting with B (or, if we do, we want to be able to expand/contract our price list to handle new/discontinued items)
Terminology for this kind of “hybrid” data structure: HashTable is an Array that “degenerates into” a LinkedList (when there are collisions)

Look How Far We Came!

Beginning of class: Only structure we knew allowing insertion (LinkedList) was $\overline{O}(n)$ for everythihg
End of class: New structure where suddenly everything is $\overline{O}(1)$, except in “unlucky” cases, in which it partially “degenerates” into a LinkedList
$\implies$ The “inevitable” $\overline{O}(n)$ runtime has transformed into the unlucky worst-case upper bound
$\implies$ By taking core data structures/algorithms from your toolkit, you can “piece together” hybrid structures whose whole (runtime) is better than the sum of its parts

Taking This Idea and Running With It

Next week we’ll look at BinarySearchTree (BST)
Since it’s just a glorified LinkedList, we’ll be able to take our HashMap from today and “drop in” the BST to play the role the LinkedList is playing right now
If collision, we’ll create a BST with its $\overline{O}(\log(n))$ operations, rather than a LinkedList with its $\overline{O}(n)$ operations
$\implies$ HashMap will go from:
- $\overline{O}(1)$ best-case but $\overline{O}(n)$ worst-case to
- $\overline{O}(1)$ best-case but $\overline{O}(\log_2(n))$ worst-case!

Hash Tables

(Spoiler alert, so you know I’m not lying to you: this is a LinkedList with some additional structure!)
You just got hired as a cashier (Safeway cashiering alum myself 🫡)
The scanner is broken (spoiler #2: the scanner uses a hash table), so you start writing down items along with their prices, one-by-one, as items come in…

Our List of (Item, Price) Pairs

Code

price_list = []
price_list.append(('Banana', 10))
price_list.append(('Apple', 2))
price_list.append(('Four Loko', 5))
price_list

[('Banana', 10), ('Apple', 2), ('Four Loko', 5)]

As the list gets longer, it gets harder and harder to find where you wrote down a specific item and its price
As you now know, you could use linear search, $\overline{O}(n)$, or if you ensure alphabetical order (an invariant!), you could use binary, divide-and-conquer search, $\overline{O}(\log_2(n))$
We can do even better: $\overline{O}(1)$. First w/magic, but then math

Strange-At-First Technique for Algorithm Analysis: Oracles

What if we had a magical wizard who could just tell us where to find an item we were looking for?
Sounds like I’m joking or saying “what if we had a billion $ and infinite aura and we could fly and walk through walls”
And yet, through the magic of math and computer science, there are concrete hashing algorithms which ensure (in a mathematically-provable way!) “almost certain” $\overline{O}(1)$ lookup time

Mathematical Strategy of Oracles

We’ll use a concrete, simplified hash function to illustrate
Mathematically we’ll be able to get something like

\[ T(n) = \overline{O}(1 + \underbrace{\epsilon}_{\mathclap{\text{Collision rate}}} \cdot n) \]

Which tells us: if we had an oracle who could ensure near-0 collision rates, then $T(n) = \overline{O}(1)$.
And, by a beautiful division-of-labor, other computer scientists figure out the near-0 collision rates part, giving us

\[ p^{✅} = [T(n) = \overline{O}(1 + \epsilon n)], q^{✅} = [\epsilon \approx 0],\text{ so } p \wedge q \implies T(n) \overset{✅}{=} \overline{O}(1). \]

Back to the Price List

Our hash function: hash(item) = first letter of item

\[ h(\texttt{x}) = \texttt{x[0]} \]

h('Banana') = 'B', h('Monkey') = 'M'
With this function in hand, we can create a length-26 array, one slot for each letter in alphabet, and then write down (item, price) pairs in whatever slot item hashes to

The Importance of Differentiating Operations: Insertion vs. Lookup

So far, we have $\overline{O}(1)$ insertion via hashing
We also get $\overline{O}(1)$ lookup!
When customer hands us an item (say, 'Banana'), we compute the hash (B), look in that slot, and obtain the price for bananas.
We also get $\overline{O}(1)$ updating (hash to find the old price, update it to have new price) and $\overline{O}(1)$ deletion (hash to find the slot containing the item, then erase it from that slot)

So What’s the Catch???

BLUEBERRIES show up to ruin our day (as usual 😞)
We hash, so far so good: h('Blueberries') = 'B'
But then we go to the B slot and see that (Bananas, 10) is already there!!! Wtf do we do here… don’t panic!
The answer? We open our HW2 from DSAN 5500 and remember that we have our lovely friend the LinkedList that we can use whenever and however we want!

Arrays vs. Linked Lists

Jeff is hiding something here… Why jump to LinkedList? Why not just… another length-26 array, for example?
For this we open up our Week 1 slides and remember the stack vs. heap distinction: we know how many letters in the alphabet, we don’t know how many items starting with B (or, if we do, we want to be able to expand/contract our price list to handle new/discontinued items)
Terminology for this kind of “hybrid” data structure: HashTable is an Array that “degenerates into” a LinkedList (when there are collisions)

Look How Far We Came!

Last week: Only structure we knew allowing insertion (LinkedList) was $\overline{O}(n)$ for everythihg
This week: New structure where suddenly everything is $\overline{O}(1)$, except in “unlucky” cases, in which it partially “degenerates” into a LinkedList
$\implies$ The “inevitable” $\overline{O}(n)$ runtime has transformed into the unlucky worst-case upper bound (feels like yesterday, all this was a dream)
$\implies$ By taking core data structures/algorithms from your toolkit, you can “piece together” hybrid structures whose whole (runtime) is better than the sum of its parts

Hash Tables: tl;dr Edition

Keys $k \in \mathcal{K}$ are plugged into a (deterministic) hash function $h: \mathcal{K} \rightarrow \{1, \ldots, N\}$, producing an index where $k$ is stored
If nothing at that index yet, store $(k,v)$ in empty slot
If already an item at that index, we have a ⚠️collision⚠️
We could just throw away the old value (HW2 Part 1)
Otherwise, need a way to store multiple items in one slot… (a way to dynamically grow storage at given index)
Solution you know so far: Linked Lists
New solution: Binary Search Trees!

Binary Search Trees

If you’ve been annoyed by how long we’ve talked about Linked Lists for… this is where it finally pays off!

BST: The Final Missing Piece

Just a glorified LinkedList! We’ll be able to take our HashMap and “drop in” the BST to play the role LinkedList is playing right now
If collision, we’ll create a BST with its $\overline{O}(\log(n))$ operations, rather than a LinkedList with its $\overline{O}(n)$ operations
$\implies$ HashMap will go from:
- $\overline{O}(1)$ best-case but $\overline{O}(n)$ worst-case to
- $\overline{O}(1)$ best-case but $\overline{O}(\log_2(n))$ worst-case!

Linked Lists + Divide-and-Conquer = BSTs

By now, the word “Linked List” should make you groan, cross your arms and start tapping your feet with impatience
“Here we go again… the Linked List is gonna make us traverse through every single element before we reach the one we’re looking for” 😖
Linked List = Canon in D
Binary Search Tree = Canon in D played by Hiromi Uehara…

Hiromi Uehara

The Metaphor Goes Deep!

Uehara’s Canon in D = Pachelbel’s + Fancier notes/rhythms on top of it
Binary Search Trees = Linked Lists + Fancier structure built on top of it
- Specifically: “next” pointer can now branch left or right, to ensure ordering of nodes

class LinkedListNode:
    @property content
    @property next

class BinarySearchTreeNode:
    @property content
    @property left
    @property right

Visualizing BSTs

Code

from hw2 import LinkedList, InventoryItem, BinarySearchTree
bst = BinarySearchTree()
item1 = InventoryItem('Mango', 50)
bst.add(item1)
item2 = InventoryItem('Pickle', 60)
bst.add(item2)
item3 = InventoryItem('Artichoke', 55)
bst.add(item3)
item5 = InventoryItem('Banana', 123)
bst.add(item5)
item6 = InventoryItem('Aardvark', 11)
bst.add(item6)
HTML(visualize(bst))

Practical Considerations

Hash Maps: Only useful if keys are hashable
- Python has a built-in collections.abc.Hashable class, such that hash(my_obj) works iff isinstance(my_obj, Hashable)
Binary Search Trees: Only useful if keys have an ordering
- “Standard” classes (int, str, datetime) come with implementations of ordering, but if you make your own class you need to implement the ordering for it!
(Linked Lists still work for non-hashable/orderable objects!)

Why `==`, `<`, `>=` “Just Work”

Not magic! Someone has explicitly written a set of functions telling Python what to do when it sees e.g. obj1 < obj2
Example: let’s implement an ordering of vectors $\mathbf{x} \in \mathbb{R}^2$ based on Pareto dominance

Ordering Vectors via Pareto Dominance

Code

class UtilVector:
    def __init__(self, u1, u2):
        self.u1 = u1
        self.u2 = u2
    
    def __eq__(self, other):
        if not isinstance(other, UtilVector):
            return NotImplemented
        return self.u1 == other.u1 and self.u2 == other.u2

    def __ne__(self, other):
        if not isinstance(other, UtilVector):
            return NotImplemented
        return self.u1 != other.u1 or self.u2 != other.u2
    
    def __gt__(self, other):
        if not isinstance(other, UtilVector):
            return NotImplemented
        return self.u1 > other.u1 and self.u2 >= other.u2 or self.u1 >= other.u1 and self.u2 > other.u2

    def __ge__(self, other):
        return self.__gt__(other) or self.__eq__(other)
        
    def __lt__(self, other):
        if not isinstance(other, UtilVector):
            return NotImplemented
        return other.__gt__(self)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)
xA = UtilVector(2, 2)
xB = UtilVector(3, 2)
print(xB > xA)
xC = UtilVector(2, 3)
print(xC > xB)
import itertools
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
x0 = UtilVector(4, 6)
util_vals = np.arange(0, 11, 0.5)
util_pairs = list(itertools.product(util_vals, util_vals))
util_df = pd.DataFrame(util_pairs, columns=['x','y'])
def compare_to_x0(row):
    row_vec = UtilVector(row['x'], row['y'])
    gt_result = int(row_vec > x0)
    lt_result = int(row_vec < x0)
    return gt_result - lt_result
util_df['greater'] = util_df.apply(compare_to_x0, axis=1)
#my_palette = sns.color_palette(['#E69F00','lightgray','#CCFFCC'])
my_palette = sns.color_palette(['#FF3535','lightgray','#35FF35'])
sns.relplot(
    data=util_df,
    x='x', y='y',
    hue='greater',
    palette=my_palette,
    marker='X', s=150
);
x0_df = pd.DataFrame({'x': [4], 'y': [6]})
plt.scatter(data=x0_df, x='x', y='y', color='black')
plt.gca().set_aspect('equal')

True
False

Back to BSTs

For HW2, we provide you with an InventoryItem class
Two instance variables: item_name and price
Equivalence relations:
- __eq__(other), __ne__(other)
Ordering relations:
- __lt__(other), __le__(other), __gt__(other), __ge__(other)
Bonus: __repr__() and __str__()

Node Traversal: Computational Tree-Climbing

LLs $\rightarrow$ BSTs: The Hard Part

When we were working with LinkedLists, we could access all items by just “looping through”, from one element to the next, printing as we go along.
But… for a BinarySearchTree, since our structure can now branch as we traverse it… How do we “loop through” a BST?
Two fundamentally different ways to traverse every node in our BST
“Opposites” of each other, so that one is often extremely efficient and the other extremely inefficient for a given task
Your job as a data scientist is to think carefully about which one is more efficient for a given goal!

Two Ways to Traverse: IRL Version

Imagine we’re trying to learn about a topic $\tau$ using Wikipedia, so we find its article $\tau_0$
There are two “extremes” in terms of strategies we could follow for learning, given the contents of the article as well as the links it contains to other articles

Depth-First Search (DFS)

Open $\tau_0$ and start reading it; When we encounter a link we always click it and immediately start reading the new article.
If we hit an article with no links (or a dead end/broken link), we finish reading it and click the back button, picking up where we left off in the previous article. When we reach the end of $\tau_0$, we’re done!

Breadth-First Search (BFS)

Bookmark $\tau_0$ in a folder called “Level 0 Articles”; open and start reading it
When we encounter a link, we put it in a “Level 1 Articles” folder, but continue reading $\tau_0$ until we reach the end.
We then open all “Level 1 Articles” in new tabs, placing links we encounter in these articles into a “Level 2 Articles” folder, that we only start reading once all “Level 1 Articles” are read
We continue like this, reading “Level 3 Articles” once we’re done with “Level 2 Articles”, “Level 4 Articles” once we’re done with “Level 3 Articles”, and so on. (Can you see a sense in which this is the “opposite” of DFS?)

…Let’s try them out! I clicked “Random Article” and got Eustache de Saint Pierre

Two Ways to Traverse: Picture Version

Code

from hw2 import IterAlgorithm, NodeProcessor
visualize(bst)

Code

print("DFS:")
dfs_processor = NodeProcessor(IterAlgorithm.DEPTH_FIRST)
#print(type(dfs_processor.node_container))
dfs_processor.iterate_over(bst)

print("\nBFS:")
bfs_processor = NodeProcessor(IterAlgorithm.BREADTH_FIRST)
#print(type(bfs_processor.node_container))
bfs_processor.iterate_over(bst)

DFS:
InventoryItem[item_name=Mango,price=50]
InventoryItem[item_name=Pickle,price=60]
InventoryItem[item_name=Artichoke,price=55]
InventoryItem[item_name=Banana,price=123]
InventoryItem[item_name=Aardvark,price=11]

BFS:
InventoryItem[item_name=Mango,price=50]
InventoryItem[item_name=Artichoke,price=55]
InventoryItem[item_name=Pickle,price=60]
InventoryItem[item_name=Aardvark,price=11]
InventoryItem[item_name=Banana,price=123]

Two Ways to Traverse: In-Words Version

Depth-First Search (DFS): With this approach, we iterate through the BST by always taking the left child as the “next” child until we hit a leaf node (which means, we cannot follow this left-child pointer any longer, since a leaf node does not have a left child or a right child!), and only at that point do we back up and take the right children we skipped.
Breadth-First Search (BFS): This is the “opposite” of DFS in the sense that we traverse the tree level-by-level, never moving to the next level of the tree until we’re sure that we have visited every node on the current level.

Two Ways to Traverse: Animated Version

**Depth-First Search** (from Wikimedia Commons)

**Breadth-First Search** (from Wikimedia Commons)

Two Ways to Traverse: Underlying Data Structures Version

Now that you have some intuition, you may be thinking that they might require very different code to implement 🤔
This is where the mathematical-formal linkage between the two becomes ultra helpful!
It turns out (and a full-on algorithmic theory course makes you prove) that

Depth-First Search can be accomplished by processing nodes in an order determined by adding each to a stack, while
Breadth-First Search can be accomplished by processing nodes in an order determined by adding each to a queue!

$\implies$ Literally identical code, “pulling out” the word stack and replacing it with the word queue within your code (or vice-versa).
If you have your Software Engineer Hats on, you’ll recognize this as a job for an abstraction layer!

Two Ways to Traverse: HW2 Version

You’ll make a class called NodeProcessor, with a single iterate_over(tree) function
This function—without any changes in the code or even any if statements!—will be capable of both DFS and BFS
It will take in a ThingContainer (could be a stack or a queue, you won’t know which), which has two functions:
- put_new_thing_in(new_thing)
- take_existing_thing_out()

Three Animals in the DFS Species

DFS Procedure	Algorithm
Pre-Order Traversal	1. Print node 2. Traverse left subtree 3. Traverse right subtree
In-Order Traversal 🧐‼️	1. Traverse left subtree 2. Print node 3. Traverse right subtree
Post-Order Traversal	1. Traverse left subtree 2. Traverse right subtree 3. Print node

The Three Animals Traverse our Inventory Tree

Code

visualize(bst)

Final Notes for HW2

The last part challenges you to ask: why stop at a hash based on just the first letter of the key?
We could just as easily use the first two letters:
h('AA') = 0, h('AB') = 1, …, h('AZ') = 25,
h('BA') = 26, h('BB') = 27, …, h('BZ') = 51,
h('CA') = 52, …, h('ZZ') = 675.
You will see how this gets us even closer to the elusive $O(1)$! And we could get even closer with three letters, four letters, … 🤔🤔🤔

Week 5: Hash Tables and Binary Search Trees

Schedule

Induction: The Core “Way of Thinking” for Algorithm Design…

The Intuition

What’s Wrong With Engineers’ Induction?

(Non-Engineers’) Induction!

Inductive Step: Can I Infer \(n + 1\) From \(n\)?

(Algorithmic/Data-Structural Proofs Almost Always Inductive!)

Core Data Structure: LinkedList

Looking Under the Hood of a Data Structure

Tuples

Lists

So, How Many “Steps” Are Required…

How Many Steps?

Visualizing LinkedLists

Onwards and Upwards: Fancier Algorithms

LinkedList: Foundation for Most(?) Data Structures!

Visualizing BinarySearchTree

So Then… Why Is This a Whole Class?

Hash Tables

Our List of (Item, Price) Pairs

Strange-At-First Technique for Algorithm Analysis: Oracles

Mathematical Strategy of Oracles

Back to the Price List

The Importance of Differentiating Operations: Insertion vs. Lookup

So What’s the Catch???

Arrays vs. Linked Lists

Look How Far We Came!

Taking This Idea and Running With It

Hash Tables

Our List of (Item, Price) Pairs

Strange-At-First Technique for Algorithm Analysis: Oracles

Mathematical Strategy of Oracles

Back to the Price List

The Importance of Differentiating Operations: Insertion vs. Lookup

So What’s the Catch???

Arrays vs. Linked Lists

Look How Far We Came!

Hash Tables: tl;dr Edition

Binary Search Trees

BST: The Final Missing Piece

Linked Lists + Divide-and-Conquer = BSTs

Hiromi Uehara

The Metaphor Goes Deep!

Visualizing BSTs

Practical Considerations

Why ==, <, >= “Just Work”

Ordering Vectors via Pareto Dominance

Back to BSTs

Node Traversal: Computational Tree-Climbing

LLs \(\rightarrow\) BSTs: The Hard Part

Two Ways to Traverse: IRL Version

Two Ways to Traverse: Picture Version

Two Ways to Traverse: In-Words Version

Two Ways to Traverse: Animated Version

Two Ways to Traverse: Underlying Data Structures Version

Two Ways to Traverse: HW2 Version

Three Animals in the DFS Species

The Three Animals Traverse our Inventory Tree

Final Notes for HW2

Core Data Structure: `LinkedList`

Visualizing `LinkedList`s

Visualizing `BinarySearchTree`

Why `==`, `<`, `>=` “Just Work”