Hashing and Binary Search Trees

7.1 Good Hash Functions and the Load Factor

7.1.1 What a Good Hash Function Buys

We last built a dictionary on top of a hash table, and we saw that multiple elements can carry the same key. When two keys land in the same bucket we call that a collision (two different keys forced into the same table cell), and to handle collisions we studied separate chaining — each bucket holds a linked list, and colliding elements are appended to the list attached to that bucket cell. Separate chaining solved the handling problem, but it leaves a question open: if we can stop collisions from happening so often, we barely need the handling machinery at all. That is why a good hash function matters.

A good hash function tries to minimize collisions as much as possible. Think about what that means for the bucket array: if collisions are rare, most of our buckets are either empty or hold just a single entry. The class was asked to put the idea into words, and the answer that landed was "equal distribution as much as possible" — the hash function should spread keys evenly over the buckets, not pile them into one corner of the table.

Why does even distribution translate into speed? If every bucket holds at most one entry, retrieving a particular element means hashing its key, walking to that one bucket, and comparing a single element. The time is constant — independent of how many elements the table holds. Retrieval becomes $O(1)$ (read "order one": the work stays the same no matter how big the table gets), which is the ideal case and the entire reason we reach for a hash table in the first place.

The flip side was shown with a small example. If we let a bad hash function pile everything into bucket 1, one bucket grows into a long linked list, and retrieving an element from that bucket means walking the list. The dictionary then degrades to the performance of a linked list and loses the advantage of that single-lookup retrieval. A good hash function is what keeps the "one lookup" promise alive.

7.1.2 The Load Factor

A good hash function minimizes collisions, but even with a good function the table fills up over time. We need a number that tells us how full the table is allowed to get. That number is the load factor.

Assume we use a good hash function to index $n$ entries in a bucket array of capacity $N$. We expect each bucket to hold about $n/N$ elements. This ratio has a name and a symbol:

The load factor $\alpha$ should be bounded by a small constant, preferably below 1. A load factor of 1 means the table is 100% full, which is not ideal; a load factor above 1 means the table has more entries than cells, which guarantees collisions. The session's standard choice is 0.75: keep $\alpha \le 0.75$ at all times.

In plain terms, the load factor is a measure of how full the hash table is allowed to get before its capacity has to be increased. When the table reaches the load factor, we grow the array — normally by doubling its size, exactly the trick we used with the dynamic array. Doubling restores the load factor to about half of the chosen bound, so the table never sits near-full for long.

7.1.3 Worked Example — How Full before Expanding

The instructor asked: if the load factor is 0.75, what does that mean? The answer: we are allowing the hash table to get 75% full — 75% of its capacity is allowed to fill before we expand.

The same reasoning carries to the load factor choice: when the load factor is reached, we double the capacity of the hash table, change the compression map to match the new size, and rehash the existing elements (the next section develops these two steps in detail). The load factor stays bounded below the constant we chose.

7.1.4 Assumptions and Scope

7.1.5 Visual Intuition — What the Table Looks Like as It Fills

Picture a bar chart of the 16 buckets of the example, with the bucket index 0 to 15 on the horizontal axis and the number of entries stored in that bucket on the vertical axis. With a good hash function the bars look almost level: most bars are 0 or 1 tall, and no bar rises far above the rest. The average bar height is exactly the load factor $\alpha =n/N$. The landmark to watch is the point where $n$ reaches $0.75\times N$: at that moment the chart is "full enough", and the growth rule replaces the whole chart with a wider one (32 bars), so every bar height roughly halves. The takeaway: the picture of a healthy hash table is a flat, low skyline — the moment tall bars appear, the hash function or the load factor is failing you.

7.1.6 Common Pitfalls

7.1.7 Student Questions and Answers

Real-world connection: every serious dictionary implementation uses exactly this design — the hash function is chosen to spread the key type evenly, the load factor is fixed at a small constant, and the table doubles (with rehashing) when that constant is hit. For example, Python's dictionaries and Java's HashMap both resize when the table crosses a load-factor threshold; the numbers differ (0.75 is common), but the mechanism is the same, and it is the reason a lookup in a dictionary of ten thousand entries takes about the same time as a lookup in one of ten.

7.2 Expected Running Time of Dictionary Operations

7.2.1 The Θ(α) Result and Its Assumption

It is tempting to say that a dictionary implemented with a hash table runs in $O(1)$ time, full stop. The instructor warned against that habit: don't blindly say the dictionary running time is constant — the claim is about the expected (average) running time, and it rests on an assumption.

The expected running time of the standard dictionary operations — find an element, insert an item, remove an element — in a hash-table dictionary is

So the correct statement has two layers:

• Expected time: $\Theta (n/N)=\Theta (\alpha )$ — it depends on how full the table is.
• Simplified claim: $O(1)$, valid only when the number of entries stays within the capacity ($n\le cN$ for a constant $c$).

The instructor pressed this point with a live question: if every bucket in the bucket array stores a single entry, what is the time taken to retrieve a particular element? One voice answered $O(n)$; the correct answer is $O(1)$ — constant time, which is the ideal case, and which is the reason we use a hash table at all. The $O(n)$ answer describes what happens when the buckets grow into long lists, which is exactly what a good hash function and a healthy load factor are supposed to prevent.

7.2.2 Why the Assumption Matters

The $O(1)$ claim silently assumes the table grows as entries arrive. The mechanism that keeps $n$ bounded by $N$ is the load-factor-triggered resize: when the table reaches (say) 75% full, we double the capacity, which restores the load factor to a small constant. The next section develops this mechanism — the compression map and rehashing — because it is what turns the conditional claim $O(n/N)$ into the unconditional "roughly constant" behavior users actually experience.

7.2.3 Assumptions and Scope

7.2.4 Visual Intuition — Time against Load Factor

Picture a graph with the load factor $\alpha$ on the horizontal axis (from 0 to 1) and the average number of steps per operation on the vertical axis. With a good hash function and chaining, the curve is a gently rising straight line: $\alpha =0.25$ gives about a quarter of a step per operation on average, $\alpha =0.75$ about three quarters, $\alpha =1.0$ about one step. The landmark is the vertical slice at $\alpha =0.75$: this is the chosen operating point, and the resize policy makes sure the table never drifts to the right of it for long. The one-sentence takeaway: keep the load factor on the left side of the graph and the expected cost stays a small constant.

7.2.5 Common Pitfalls

7.2.6 Student Questions and Answers

Real-world connection: this conditional $O(1)$ is why database and search-engine index structures report "expected constant time" lookups rather than flat guarantees, and why production hash tables (in standard libraries of languages like Python, Java, and Go) all ship with a built-in growth policy. The engineering lesson: the hash function and the growth policy are one system — a fast hash function with no resize discipline still collapses to linear-time behavior under enough data.

7.3 The Compression Map and Rehashing

7.3.1 Compression Mapping

Recall the two-step pipeline of a hash table. First the hash code mapping converts keys to integers. Then the compression mapping converts those integers into the range

$$[0,N-1]$$

— that is, into valid bucket indices. Every bucket array of capacity $N$ has cells numbered $0,1,\dots ,N-1$, so $N-1$ is the last (highest) valid index.

7.3.2 Why Rehashing Is Necessary

Keeping the load factor below the chosen constant (say 0.75) requires growing the bucket array. But growing $N$ breaks the compression map — a map that produced indices in $[0,N-1]$ is now working with a new, larger $N$. So whenever we increase the size of the bucket array, we must also change the compression mapping to match the new size.

That, in turn, forces a second step: we must insert all the existing hash-table elements into the new bucket array using the new compression mapping. The position of an element can change when $N$ changes, even though the element was already hashed and stored. Re-hashing those existing elements into the new array is called rehashing. It is not optional: when you increase the size of the bucket array, you have to rehash. A good choice for the new size is to double the size of the original array.

Rehashing means two things, and the instructor stressed both: (1) double the array size, and (2) rehash the elements already present in the initial hash table — they may need new locations.

7.3.3 Worked Example — Collisions Degrade Performance (N = 4)

7.3.4 Worked Example — A Full Rehash Walkthrough (N = 6 → 12)

7.3.5 Assumptions and Scope

7.3.6 Visual Intuition — The Bucket Array Before and After

Picture the bucket array as a row of boxes with a label over each one, and the hash function as the rule "look at the label on the box". With $N=6$, the labels are 0 through 5, and Elephant (8 characters) reads label 2. After doubling, the row has twelve boxes labeled 0 through 11; Elephant now reads label 8 — the old label 2 is still there, but the rule points elsewhere. The visual landmark is the moment of the switch: at the same instant the row doubles in length, every element walks to its new box under the new labels. The one-sentence takeaway: the array doubles and the elements redistribute in a single synchronized step; elements whose new bucket differs are the visual proof that the old positions are meaningless under the new size.

7.3.7 Common Pitfalls

7.3.8 Student Questions and Answers

Real-world connection: the instructor illustrated rehashing with how cloud storage accounts behave — the same pattern used by providers such as Dropbox. When you buy a large storage allotment, the provider does not hand you the complete capacity at once. They allot a portion — roughly half of what you asked — and when your usage reaches about 75 percent of what has been allotted, a notification fires ("this user has used this much") and they double the allotted capacity. The allotment grows incrementally, exactly the way the hash table doubles its capacity at the load factor. Compared with the cost of allotting complete storage initially, the incremental cost of rehashing is acceptable.

7.4 Open Addressing — an Overview

7.4.1 The Idea — the Table Is Open to Colliding Items

Separate chaining is one method of handling collisions, but it may not always be the right one, for reasons that become clear once we see the alternative. The next method is open addressing. The name can mislead: open addressing does not mean the table is "open" in any loose sense. It means the hash table is open to the colliding item as well — the colliding item is placed in a different cell of the same table.

Compare the two. In separate chaining, whenever there is a collision we attach a list to the bucket cell and store the colliding item in that list — a separate structure outside the bucket array. In open addressing, the item and the colliding item are placed in the same bucket array, at different locations. There is no secondary structure; the colliding key just lives in another cell of the same array.

7.4.2 The Space Trade-off

The immediate payoff of open addressing is space: no extra ADTs, no linked lists, no auxiliary structures. We save space — useful when we are short of space. The cost is on the other side of the ledger: the complexity of dealing with collisions is higher, because finding that other cell takes work, and so does searching for it later. So the trade-off is clean — if you don't manage more space, open addressing is the approach; if you can afford the extra structure, separate chaining keeps collision handling simpler.

7.4.3 The Three Methods

Under open addressing there are three methods, which the session covered one by one:

1. Linear probing — place the colliding item in the next available cell.
2. Quadratic probing — probe cells at squared offsets from the original hash.
3. Double hashing — use a second hash function to compute the probe step.

All three are "simple methods", as the instructor put it, and each has its own failure mode — the next sections develop each one with full examples.

7.4.4 Comparison — Separate Chaining vs Open Addressing

The one-sentence rule for choosing: if you can afford the extra structure, separate chaining keeps collision handling simple; if you are short of space, open addressing saves memory and you pay with probe arithmetic.

7.4.5 Visual Intuition — One Array, Two Ways of Filling

Picture a row of cells. Separate chaining draws a chain hanging below a cell whenever two keys land there — the picture grows downwards, out of the array. Open addressing instead fills sideways: a colliding key moves to a neighbouring cell (linear), jumps to a squared-off distance (quadratic), or hops by a key-dependent step (double hashing). The visual landmark is the same in all three: no structure grows outside the row, and the row itself gradually fills. The takeaway: open addressing turns the "overflow area" of chaining into probe arithmetic inside the same array.

Real-world connection: open addressing is the layout behind many in-memory hash tables and caches, including parts of CPython's dictionary implementation and several database buffer pools — places where memory is scarce, locality matters, and chaining's pointer chasing would cost extra cache misses.

7.5 Linear Probing

7.5.1 The Probing Rule

Linear probing handles collisions by placing the colliding item in the next available table cell — more precisely, the next circularly available table cell, with all positions taken mod $N$. Don't forget the mod: the search wraps around the end of the array.

The insertion rule in full: hash the key with $H(K)$. Whatever index you get, check that cell first. If the location is available, place the item there. If it is not, check the next cell, then the next, moving through the array until an empty bucket accepts the new entry.

7.5.2 Worked Example — Insert 18, 41, 22, 44, 59, 32

7.5.3 Searching in a Linear-Probed Table

The extra complexity of linear probing shows up at search time. To search for a key $K$, apply the same hash function and probe the same circular sequence — you cannot stop at the first occupied cell.

The reason we must keep probing: a displaced key never sits where its hash value points — it sits further along the probe sequence, and the only way to reach it is to walk the same sequence the insertion walked.

The rule: probe until you find the key or until you find an empty cell. This stopping rule is the search analog of the load-factor discipline from Section 7.1 — the load factor has to be considered, because you can fill the array only up to the load factor (0.75 or whatever you kept); you never let the table get so full that searches walk long distances.

7.5.4 The Find and Insert Algorithms

7.5.5 Assumptions and Scope

7.5.6 Visual Intuition — The Wrap-Around Scan

Picture the 13 cells of the example as a clock face numbered 0 to 12, with the hand starting at the hash value. Insertion moves the hand clockwise, cell by cell, until it lands on a free cell; the hand may cross the top of the clock (cell 12 back to cell 0) — that crossing is the $\mathrm{mod}N$ wrap. Search starts the hand at the same place and moves it clockwise, cell by cell, stopping when it finds the key or hits a gap. The landmark to notice: a key that collided at cell 6 may finally sit at cell 8 — so on the clock face, "where is 32?" is answered by sweeping the arc 6 → 7 → 8, not by looking at 6 alone. The one-sentence takeaway: linear probing is a clockwise sweep from the hash value, and a gap ends the sweep.

7.5.7 Common Pitfalls

7.5.8 Student Questions and Answers

Real-world connection: linear probing is the collision strategy inside several real hash tables because it has the best cache behavior — consecutive cells are nearby in memory, so probing walks a contiguous cache line instead of chasing pointers. CPython's dictionaries and Ruby's hash tables use open addressing variants with this locality advantage; the price they pay is exactly the discipline of this section: keep the load factor bounded, or the sweep becomes a scan.

7.6 Deletion in Open Addressing

7.6.1 The Available Marker

To handle insertions and deletions in an open-addressed table, we introduce a special object called available, which replaces deleted elements. The removal procedure: first search for an item with key $K$ — applying the same hash function used at insertion and probing the same sequence. If the item is found, replace it with the special item available and return the element $E$. The cell is marked, not emptied.

Why the marker? If we simply delete the element and keep the location empty, the find operation would mistake that location for an initially empty cell. Consider a search that is probing for some other element and reaches the deleted cell: it would think this location was empty from the beginning, stop the search there, and report that the element is not found — even though the real answer sits further along the probe sequence. So we must be very clear when a location was deleted: the available marker distinguishes a deleted location from an initially empty one. A search continues past available cells (they are not "empty" for search purposes) but stops at truly empty cells; an insert can use either an empty cell or an available cell.

7.6.2 Worked Example — Deletion and the Available Marker

7.6.3 Assumptions and Scope

7.6.4 Visual Intuition — Three Kinds of Cells

Picture the bucket row with cells painted in three colors: white for never-used, gray for occupied, and striped for deleted-but-available. A search walks right from the hash position and stops at the first white cell; striped cells are just part of the road. The visual landmark is a striped cell sitting between two occupied cells — it proves a key was removed, and it is precisely the cell that would have broken the sweep if it were white. The takeaway: the marker turns "this cell has no key" (empty) into "this cell has no key and never did" (empty) versus "a key was here once" (available) — three meanings, one bit of bookkeeping.

7.6.5 Common Pitfalls

7.6.6 Student Questions and Answers

Real-world connection: the available (deleted) marker is standard practice in production open-addressed tables — for example, in systems where keys expire or records are removed (caches, session stores). When such tables fill with markers, real implementations trigger a rehash that also purges markers, which is why the delete-heavy workloads in databases and caches are usually better served by chaining or by a different structure entirely.

7.7 Primary Clustering

7.7.1 What Primary Clustering Is

Linear probing has a characteristic failure mode called primary clustering. The instructor showed it with a sequence of insertions, then asked the class to name the pattern.

Consider inserting the keys 18, 41, 22, 44, 59, 32, 31, 73 into an initially empty table of size 13 with $H(K)=K\mathrm{mod}13$:

• 18 → 5; 41 → 2; 22 → 9.
• 44 → 5 (occupied) → 6.
• 59 → 7.
• 32 → 6 (occupied) → 7 (occupied) → 8.
• 31 → 5 (occupied) → 6, 7, 8, 9 all occupied → 10.
• 73 → 8 (occupied) → 9 (occupied) → 10 (occupied) → 11.

Cells 5 through 11 are now one solid block. Every one of these keys originally hashed to 5, 7, 8, or 9, and linear probing stacked them into a contiguous run.

Primary clustering is the tendency of elements to cluster around the table locations they originally hashed to. Elements like 44, 31, and 32 all wanted to sit near their initial hash values (5, 5, 6), and the collision-resolution rule placed each one immediately after the last collider, so the consecutive locations get filled. There may be empty locations elsewhere in the table — but the colliding items all pile up next to the values they originally hashed to, producing a cluster.

7.7.2 Worked Example — All Keys Hash to the Same Value (N = 17)

7.7.3 Worked Example — The Outsider Suffers

7.7.4 Assumptions and Scope

7.7.5 Visual Intuition — The Growing Block

Picture the 17-cell table as a row of boxes. The multiples of seventeen all drop into box 0, so the overflow spreads right: box 0 fills, box 1 fills, box 2 fills — a solid block creeping rightward while boxes 7 through 16 stay empty. The landmark is the frontier of the block: every new collider pushes the frontier one step right, and any outsider whose hash value lies inside the block (like 20 at cell 3) must traverse the entire block to get past it. The one-sentence takeaway: a cluster is a contagious block — colliders extend it, and innocents must pay to cross it.

7.7.6 Common Pitfalls

7.7.7 Student Questions and Answers

Real-world connection: primary clustering is the textbook reason real systems do not use plain linear probing on unknown workloads — the danger is precisely the "everybody piles onto the same corridor" failure that shows up in memory allocators and caches under skewed access patterns. Systems that must survive adversarial or skewed key distributions prefer quadratic probing or double hashing, or fall back to chaining, all to avoid the block-of-cells failure you saw here.

7.8 Quadratic Probing

7.8.1 The Probing Sequences

Quadratic probing is the second open-addressing strategy, and it is a small variation on linear probing. Instead of probing $i,i+1,i+2,\dots$ away from the hash value, we probe at squared offsets. Two equivalent forms were used in the session:

7.8.2 Worked Example — Insert 76, 40, 48, 5, 55

7.8.3 The Consistency Rule

You may choose either $(H(K)+i^2)\mathrm{mod}N$ or $(H(K)+i+i^2)\mathrm{mod}N$, but you must use the same one for all elements and all probes. Using $(H(K)+i^2)$ for one element and $(H(K)+i+i^2)$ for the next is wrong — as is combining linear and quadratic probing in a single solution. Think about retrieval in a real system: we insert using one probing rule and retrieve using another — then we would have to remember which elements were inserted with which method. That cannot be done, so we never unnecessarily increase the complexity; the probe function stays consistent.

7.8.4 Assumptions and Scope

7.8.5 Visual Intuition — Jumping Farther Each Time

Picture the 7-cell table as a row of boxes, with the hash position as a start point. Linear probing's sweep takes steps of 1, 1, 1; quadratic probing takes steps of 2, 4, 6, 8, … (that is, the offsets $i^2$ grow as $1,4,9,16,\dots$, and the difference between successive offsets is $2i+1$). The visual signature is a jump that gets longer each probe: 48 jumps from cell 6 to cell 1 in one bound; 55 jumps 6 → 1 → 5 → 4, hopping over the occupied stretch instead of inching through it. The takeaway: squared offsets scatter the probes widely, which is why clusters do not grow as contiguous blocks — and why the same spread can miss cells entirely.

7.8.6 Common Pitfalls

7.8.7 Student Questions and Answers

Real-world connection: quadratic probing appears in real hash tables where cache-friendly sequential probes are not essential but adversarial skew must be damped — for example, in several database hash indexes and in the hash tables of some runtimes. The consistency rule is an engineering invariant, not just an exam rule: production tables store the probe parameters inside the table header, so that a table rebuilt with different parameters is always searched with the same parameters that built it.

7.9 Secondary Clustering

7.9.1 What Secondary Clustering Is

Quadratic probing cures one problem and inherits another. It fixes the bleed-over effect of primary clustering: a key that hashes to a value outside the cluster no longer suffers the cluster's probe sequence. But it introduces secondary clustering: all elements that hash to the same initial value follow the same probe sequence — the same offsets $i+i^2$ (or $i^2$) from the same starting cell. So the collision resolution for every member of a group is identical, and the group still collides with itself, just in a different pattern.

The deeper problem: quadratic probing may fail to find an empty slot even when the array is not full. The probe sequence revisits only certain cells (the squared offsets modulo $N$), so the insertion loop can run through its probe set and find every candidate occupied — while plenty of cells elsewhere in the array sit empty. This is especially true when $N$ is not chosen as a prime: then we may be unable to find an empty slot even when the array is at least half full. We may have half the locations empty and still cannot place the element, because the probe sequence keeps returning to occupied cells.

7.9.2 Worked Example — The Same Keys, Quadratically

7.9.3 Why a Prime N Helps

Choosing $N$ prime mitigates the failure. With a composite modulus, the sequence $(H(K)+i+i^2)\mathrm{mod}N$ (or $i^2$) revisits only a fraction of the cells; with a prime $N$, the mod-N wrap-around reaches far more distinct locations before repeating. As the instructor put it: if you choose $N$ as prime, at least you may be able to find more locations compared to a non-prime $N$, because the mod $N$ makes the probe cycle visit more distinct cells. The earlier session's example of why $N$ should be prime applies here directly.

7.9.4 Assumptions and Scope

7.9.5 Visual Intuition — One Track, One Group, Repeated Hops

Picture the 17-cell table as a circular track with markers 0 to 16. The multiples-of-17 group all start at marker 0 and hop to 2, then 6, then 12, then 3, then 13, then 8 — leaving marks only on this one track while markers 1, 7, 9, 10, 11, 14, 15, 16 stay untouched. A key that starts at marker 3 (an outsider) hops 3, 5, 9, 15, 6, ... — a different set of markers. The landmark is the untouched markers: a visitor inspecting the table sees large empty regions and still cannot place the next group member, because the group's track is exhausted. The takeaway: secondary clustering is a group-local exhaustion of one probe track, not a contagious block.

7.9.6 Common Pitfalls

7.9.7 Student Questions and Answers

Real-world connection: the prime-capacity rule is a hard engineering constraint in real hash tables — production tables size their arrays to prime (or near-prime) lengths, and when a table grows it often grows to the next prime rather than to a power of two, for exactly the reason of this section: the probe cycle must spread over distinct cells. Hash-table libraries for languages such as Java and C++ document prime table sizes; the trade-off is that resize math becomes slightly costlier, which is the price of avoiding group-local starvation.

7.10 Double Hashing

7.10.1 Two Hash Functions

Double hashing is the third open-addressing method, and the instructor's verdict was "simple — just a little more arithmetic". We use two hash functions. The first is the ordinary one, $H(K)$, which gives the starting cell. Whenever there is a collision, we compute a second hash function $H^{\prime }(K)$, and the probe sequence becomes

7.10.2 Worked Example — Insert 18, 41, 22, 44, 59, 32

7.10.3 Assumptions and Scope

7.10.4 Visual Intuition — Different Strides, Different Tracks

Picture two runners starting at the same cell on a circular track of 13 markers. Under linear probing both shuffle one marker per probe and stay side by side forever; under double hashing one runner's stride is 5 (44's stride) and another's is, say, 3 — after the first step they are already on different markers, and their paths never coincide again. The visual landmark is the first probe: keys with the same starting cell take their first step in different directions by different distances. The takeaway: the second hash creates per-key tracks, which is why double hashing avoids both primary and secondary clustering.

7.10.5 Common Pitfalls

7.10.6 Student Questions and Answers

Real-world connection: double hashing is the method behind several high-performance hash tables where insertions are frequent and lookups must stay short — for example, in parts of the Linux kernel's hash table infrastructure and in some in-memory databases. Its per-key stride makes it the recommended open-addressing method under adversarial key sets, because no single group can monopolize a probe track; the price is two hash computations per collision, which modern CPUs absorb easily compared with the cost of a cache miss on a long cluster.

7.11 Complexity of Hashing — Worst Case and Expected Probes

7.11.1 The Worst Case

Many students, as the instructor noted, had not noticed until this session that the constant-time claim is conditional. The worst case for search, insertions, and removals on a hash table is

$$O(n)$$

When does the worst case occur? When all the keys inserted collide — every key hashes to the same cell, every operation walks the whole pile. If the data guarantees this behavior, the hash table delivers nothing but linear work, and the honest engineering decision is to not use a hash table for that data at all. The load factor is the control knob: it affects the performance of the hash table directly, because it bounds how long the chains (or probe runs) can grow before the table resizes.

7.11.2 The Expected Number of Probes

On the expected side, there is a classic result. Assuming the hash values behave like random numbers, the expected number of probes for an insertion with open addressing is

$$\frac{1}{1-\alpha }$$

This is the average number of cells you have to inspect before you can insert an element (equivalently, the expected number of probes to search for an element that is not present). The proof is a standard theorem — it appears in the Cormen reference textbook (CLRS) for those who want to see it.

Notice what the formula says: as the load factor approaches 1, the expected probes grow without bound — $1/(1-\alpha )\to \infty$. That is the mathematical reason the load factor must be kept below a constant like 0.75: it is not a style choice, it is what keeps open addressing efficient. (For searching for a key that is present, the standard companion result is $\frac{1}{\alpha }\ln \frac{1}{1-\alpha }$ probes — a slightly smaller number, since successful searches stop earlier on average.)

7.11.3 Assumptions and Scope

7.11.4 Visual Intuition — The Explosion near 1

Picture a graph with the load factor $\alpha$ on the horizontal axis from 0 to 1, and the expected number of probes on the vertical axis. The curve is flat near the left — at $\alpha =0.25$ it is about 1.33 probes — and climbs gently through $\alpha =0.5$ (2 probes) and $\alpha =0.75$ (4 probes). Then, just before $\alpha =1$, the curve turns sharply upward and runs off the top of the graph — at $\alpha =0.9$ it is already 10 probes, and it has no finite value at $\alpha =1$. The landmark is the vertical asymptote at $\alpha =1$: the curve never touches it, and the growth policy exists to keep the table far left of it. The one-sentence takeaway: the cost curve is tame until the last few percent of fullness, then explodes — the load-factor bound is the guardrail at the cliff.

7.11.5 Common Pitfalls

7.11.6 Student Questions and Answers

Real-world connection: the expected-probes formula is why system designers quote "constant expected time" for hash lookups and why load-factor policies are tuned to fractions like 0.7–0.9 in production systems — every table from in-memory caches to database indexes chooses its bound on this curve. And the worst-case warning is the reason high-security systems use randomized hashing (a secret per-process seed) or trees for key lookups: when an attacker can engineer collisions, the O(1) promise is exactly what gets weaponized.

7.12 Binary Search Trees — Definition and Property

7.12.1 The BST Property

We shift from hashing to the second half of the session: binary search trees. A binary search tree (BST) is a binary tree that stores keys at its internal nodes and satisfies the following property. Let $u$, $v$, $w$ be three nodes such that $u$ is in the left subtree of $v$ and $w$ is in the right subtree of $v$. Then

$$\mathrm{key}(u)<\mathrm{key}(v)\le \mathrm{key}(w)$$

In plain words: every key in the left subtree of a node is smaller than the node's key, and every key in the right subtree is larger than (or equal to) the node's key. The instructor's one-line restatement: the keys on the left of a node will be smaller than the node, and the keys on the right will be larger than the node. That's it — a binary search tree is a binary tree that satisfies this property. The ordering holds not just against the immediate children but against every ancestor: the property applies to whole subtrees, which is exactly the point students later miss in the exam question of Section 7.19.

The professor writes the left side with a strict "less than"; the standard textbook treatment writes $\mathrm{key}(u)\le \mathrm{key}(v)\le \mathrm{key}(w)$, allowing equal keys to sit on either side. For distinct keys — the case in this session's examples — the two forms are identical, and the lecture's version is the one to use on the exam.

7.12.2 Inorder Traversal Visits Keys in Order

Because of the BST property, an inorder traversal — the traversal where the root sits in the middle, left subtree, then root, then right subtree — visits the keys in increasing order. For the example tree shown in the session (root 6; left child 2 with children 1 and 4; right child 9 with left child 8), the inorder traversal produced 1, 2, 4, 6, 8, 9: strictly ascending. This ordering fact is the engine behind rank (Section 7.18), successor and predecessor (Section 7.15), and the kth-smallest algorithm.

7.12.3 The External-Node Convention

The trees in the material follow the Goodrich textbook convention: external nodes do not store items. The slides draw external-node squares at the bottom of the tree — these external nodes are not real data-bearing nodes, and the instructor was explicit: don't get confused by them, we are not going to store items in them, we ignore them. They exist only to keep the tree representation uniform. (Search and insertion will treat them as the empty positions where a search path ends.)

7.12.4 Assumptions and Scope

7.12.5 Visual Intuition — A Tree That Reads Left to Right

Picture the session's tree:

        6
       / \
      2   9
     / \  /
    1  4 8

The BST property paints a picture: at every node, everything hanging to the left is smaller, everything to the right is larger. The landmark is the left-to-right sweep: if you shrink the tree down to one line, left-to-right, you get 1, 2, 4, 6, 8, 9 — the sorted order. The empty squares at the bottom are the external nodes: empty sockets that show where a search would stop or an insertion would land, holding no keys of their own. The one-sentence takeaway: a BST is a sorting machine shaped like a tree — read it left to right and the keys come out sorted.

7.12.6 Common Pitfalls

7.12.7 Student Questions and Answers

Real-world connection: BSTs are the shape behind ordered maps and ordered sets in standard libraries (for example, the ordered containers in C++ and Java) and behind the sorted index structures of many databases. The property of this section is what lets those structures answer "is this key present?" and "what is the next key?" in logarithmic time — the exact operations the rest of this half of the session develops.

7.13 Searching in a BST

7.13.1 The Downward Path

To search for a key $K$, trace a downward path starting at the root. At each node $v$, compare $K$ with $\mathrm{key}(v)$: if $K<\mathrm{key}(v)$, the key — if present — must lie in the left subtree; if $K>\mathrm{key}(v)$, it must lie in the right subtree; if equal, we have found it. One whole subtree is discarded at every step, and that is what makes the search fast.

The BST property is doing the work: because every left-subtree key is smaller than the node and every right-subtree key is larger, a single comparison at each node tells us which half of the remaining tree could possibly contain $K$. Searching a BST is exactly the tree-shaped version of binary search on a sorted array: each step picks the left or right half and throws the other half away.

7.13.2 Worked Example — Find 4

        6
       / \
      2   9
     / \  /
    1  4 8

7.13.3 The Recursive Algorithm and Its Analysis

The search algorithm is recursive and compact. With $T$ the current (sub)tree and $v$ its root node:

7.13.4 Assumptions and Scope

7.13.5 Visual Intuition — Halving the Tree at Every Level

Picture the search for 4 on the tree above as a flashlight beam shining down from the root: at node 6 it lights only the left branch (the right branch goes dark), at node 2 only the right branch, and at node 4 the beam stops. At each level exactly one of the two branches remains lit, so the number of visited nodes equals the height of the tree — the depth of the beam, not the size of the tree. The landmark is the discarded subtrees: with 6 nodes, the search touched 3 and ignored 3. The one-sentence takeaway: a BST search is a single root-to-leaf beam, and its length — the height — is the entire cost.

7.13.6 Common Pitfalls

7.13.7 Student Questions and Answers

Real-world connection: BST search is the mechanism inside ordered-map lookups in standard libraries and database ordered indexes — the same "follow one path, discard half" idea that makes phone-directory lookup, autocomplete tries, and binary-search-adjacent structures fast on ordered data.

7.14 Inserting into a BST

7.14.1 The Insertion Procedure

To insert a new key $K$ (assume the key is not already in the tree): search for $K$ exactly as in Section 7.13. The search ends at a leaf position — an external node $W$ — where the key would live. Insert the new key $K$ at node $W$, and expand $W$ into an internal node. In other words: follow the path the key would take, and the new node lands at the leaf position where the search stops.

7.14.2 Worked Examples — Insert 5 and Insert 10

        6
       / \
      2   9
     / \  /
    1  4 8

7.14.3 Assumptions and Scope

7.14.4 Visual Intuition — Growing One New Leaf

Picture the tree as a mobile hanging from the root 6. Inserting 5 means walking down the wire to 6, then down the left wire to 2, then to 4, and clipping a new leaf to the right of 4; inserting 10 clips a new leaf to the right of 9. The visual landmark: the new node always hangs at the bottom — the tree never gains an internal slot, only a new dangling leaf at the end of an existing path. The one-sentence takeaway: insertion is "search, then grow" — the search path decides the spot, and the tree grows only at the bottom.

7.14.5 Common Pitfalls

7.14.6 Student Questions and Answers

Real-world connection: this grow-at-the-leaf insertion is how ordered containers accept new entries — databases insert index keys, phone books add subscribers, calendars add events — all by the same "walk and plant" rule. Because the shape is never corrected, real systems pair this insertion with a balancing scheme; the next sections show what can go wrong without one.

7.15 Inorder Successor and Predecessor

7.15.1 Definitions

The inorder traversal of a BST gives the keys in ascending order. Using that ordering:

• The inorder successor of a key is the smallest number which is larger than the key — the element just after it in the inorder traversal.
• The inorder predecessor of a key is the largest number which is smaller than the key — the element just before it.

A useful memory trick offered in the session: successor means large, so it lives in the right subtree; predecessor means small, so it lives in the left subtree. Within the right subtree the successor is the leftmost node; within the left subtree the predecessor is the rightmost node.

7.15.2 The Rules for Locating Them

For a node $v$:

7.15.3 Worked Examples

         15
        /  \
       10   20
      / \   / \
     8  12 16 25

         20
        /  \
       8    30
        \   /
        12 25
         \
         14

7.15.4 Assumptions and Scope

7.15.5 Visual Intuition — The Two Mirrored Walks

Picture Tree 2: successor and predecessor are mirror images. To find the successor of 14, walk right one step... there is no right child, so climb the left spine: 14 → 12 (a right child — not it), → 8 (a left child — yes), and the answer is the parent of 8, which is 20. The climb rule reads like a signpost: keep climbing while you are coming up from the right; the first time you come up from the left, that parent is the answer. The landmark is the direction of the final climb — "came up from the left" for successor, "came up from the right" for predecessor. The takeaway: successor climbs until the node is a left child; predecessor climbs until the node is a right child.

7.15.6 Common Pitfalls

7.15.7 Student Questions and Answers

Real-world connection: successor and predecessor queries are what ordered structures use to answer "what is the next larger key?" — the operation behind range queries in databases, floor/ceiling lookups in ordered sets, and navigation between adjacent entries in sorted indexes.

7.16 Deleting from a BST

7.16.1 Case 1 — No Children

Deleting a node with no children is trivial: just delete the node. For example, deleting 18 from the session tree — 18 has no children — so simply remove it. Nothing else changes.

In the external-node convention, deleting a leaf means removing the internal node and letting its two external nodes collapse back into one — the tree simply shrinks by one leaf, and every remaining subtree keeps its ordering.

7.16.2 Case 2 — One Child

Deleting a node with one child: remove the node and replace it with its child. There is nothing to check — the child simply takes the deleted node's place, and the BST property is preserved because the child was already in the correct subtree.

Two worked examples: delete 25, which has a single child 30 → replace 25 with 30. Delete 4, which has a single child 5 → replace 4 with 5. (In the material's drawings, the empty rectangles around such nodes are just the external-node convention of Section 7.12.3 — if the rectangles confuse you, ignore them.)

Why is no check needed? The child was already a valid member of the deleted node's subtree: everything in the child's left subtree was smaller than the child, everything in its right subtree larger, and the child itself was already correctly placed relative to the deleted node's parent. Splicing the child up into the parent's slot keeps every ancestor ordering intact.

7.16.3 Case 3 — Two Children

This is where the successor/predecessor concept pays off. To delete a node with two children, replace that node with its inorder successor or its inorder predecessor — whichever you choose, the result is still a BST. Why replace at all? To restore the BST property: the replacement node is the one value that can take the deleted node's place without violating the ordering.

The instructor's explanation of why this works: the predecessor is the largest value smaller than the key, and the successor is the smallest value larger than the key — exactly the two candidates that can occupy the deleted node's position and keep every subtree ordered. So case 3 = delete, replace with successor or predecessor (follow one convention), and the BST property is automatically restored.

7.16.4 Assumptions and Scope

7.16.5 Visual Intuition — Splicing Out a Node

Picture the three cases as three kinds of surgery. A leaf is plucked away — the tree loses one twig. A one-child node is replaced by its child — the child slides up into the parent's slot like a branch being grafted upward one level. A two-child node is the interesting one: instead of removing it (which would open a hole with no obvious filler), we copy the value of its neighbor in sorted order (the successor, the smallest thing to its right — or the predecessor, the largest thing to its left) into the node, then delete that neighbor, which is a leaf or near-leaf. The visual landmark: the deleted value disappears, but the node's shape stays occupied by its sorted neighbor — the tree keeps its structure and only the labels change. The takeaway: case 3 is "steal a neighbor's value, then delete the neighbor, never the two-child node itself".

7.16.6 Common Pitfalls

7.16.7 Student Questions and Answers

Real-world connection: this delete procedure is the exact code path in ordered map libraries when a user removes a key — the "steal the successor's value" trick keeps such containers correct with minimal restructuring, and it is the reason balanced variants (AVL, red-black) can limit themselves to a handful of rotations after deletion rather than rebuilding the tree.

7.17 BST Performance — Balanced Trees and Skewed Trees

7.17.1 The Skewed Tree

The $O(\log n)$ claims of the previous sections assume the tree stays balanced. The BST property does not force balance — insertion order does. If the keys are inserted in sorted order — 1, 2, 3, ... — each new key is larger than all previous ones, so each insertion goes to the rightmost position, and the tree ends up as a skewed tree: every node has one child, and the tree is really a list in disguise. The height becomes $n$ instead of $\log n$, and every operation degrades to

$$O(n)$$

The answer is the insertion order. The BST property says nothing about shape: it only says where a key may sit relative to another. Inserting keys in ascending order is the worst possible case — every new key is larger than everything present, so every insertion descends to the far right and hangs a new rightmost leaf, building a chain of $n$ nodes with height $n$.

1
 \
  2
   \
    3
     \
      4
       \
        5

7.17.2 Complexity in Both Worlds

• Balanced BST: search, insert, delete, successor, predecessor all in $O(\log n)$ — height of the tree, log base 2 of $n$.
• Skewed BST (sorted insertions): all operations in $O(n)$ — height equals the number of keys.

The one-sentence rule for choosing: a BST with random or interleaved insertion order gives logarithmic behavior; a BST fed sorted (or reverse-sorted) data degenerates to the speed of a linked list — which is exactly why balanced variants exist.

The instructor's remark: BST performance can be skewed like this, and the fix belongs to the balancing material that follows the basic BST discussion. For the purposes of this session, the balanced analysis is what carries the $O(\log n)$ claims, and the skewed case is the warning that insertion order matters.

7.17.3 Visual Intuition — The Tree That Lies Down

Picture the balanced tree as a triangle: 7 nodes, three levels, every search path about three steps. Now picture the same keys inserted in sorted order: the triangle collapses into a diagonal staircase — each node has one right child and no left child, so the "tree" is drawn as a single diagonal line. The landmark is the left subtrees: in the skewed tree every left subtree is empty, which is the tell-tale of sorted insertion. The one-sentence takeaway: the height of the tree is the ruler of all BST costs, and insertion order is the hand that bends the ruler.

7.17.4 Assumptions and Scope

7.17.5 Common Pitfalls

Real-world connection: the skewing warning is the direct reason standard libraries never ship plain BSTs — the ordered containers in C++, Java, and Go use self-balancing trees (red-black, AVL, or treaps) so that no insertion order can degrade them. Database indexes face the same threat: time-ordered keys (timestamps, auto-increment IDs) are exactly the sorted-insertion pattern that would skew a plain BST, so real indexes use balanced or logarithmic structures.

7.18 The Kth Smallest Element in a BST

7.18.1 Rank — Position in the Inorder Traversal

The rank of an element is its position in the inorder traversal. In the session's example tree (keys 2, 6, 7, 8, 10, 15, 18, 20 in inorder), rank of 2 is 0, rank of 6 is 1, rank of 15 is 5, rank of 20 is 7 — counting positions starting at zero. Because the inorder traversal is sorted (Section 7.12.2), the element of rank $r$ is exactly the $(r+1)$-th smallest element. This is the concept the kth-smallest algorithm is built on.

7.18.2 The Algorithm

7.18.3 Worked Example — The 4th Smallest Element

The instructor's insight: you do not need to memorize this algorithm by heart. It is only built on the BST property — the number of left elements tells you how many elements are smaller than the node, so comparing $k$ with that count tells you which side of the tree the answer is on. Understand that, and the algorithm writes itself.

7.18.4 Assumptions and Scope

7.18.5 Visual Intuition — The Ruler of the Left Counts

Picture the tree as a ruler where the left-subtree count at each node is a milestone: at node 20 the milestone says "7 elements stand before me", at node 10 it says "4", at node 6 it says "1". The walk for $k=4$ reads these milestones like a game of "hotter, colder": at 20, the milestone (7) is too big, so the answer is deeper; at 10, the milestone (4) equals the current $k$, and since $4>4$ is false we go left; at 6, the milestone (1) is smaller than $k$, so we subtract and swing right; at 8, the milestone (1) makes the updated $k=2$ equal $1+1$. The landmark is the subtraction step: the only moment the walk turns right. The takeaway: the left counts are a running scoreboard, and the answer is the node where the scoreboard finally equals $k$.

7.18.6 Common Pitfalls

7.18.7 Student Questions and Answers

Real-world connection: the kth-smallest operation is a "select" query — the same primitive used to find percentiles and medians in ordered data structures, from database query engines computing median salaries to analytics finding the 95th-percentile latency of a service. Ordered containers with subtree-size augmentation answer such queries in logarithmic time, which is why median/percentile lookups stay fast even on huge datasets.

7.19 Past Exam Question — Which BST Does an Insertion Order Produce?

7.19.1 The Question and the Common Mistake

A past exam question gives an insertion order and four candidate BSTs: "suppose the keys are inserted into a binary tree in this order — which of the following is the BST that is formed?" The catch is the phrase inserted in this order: the first key becomes the root, and every later key is placed by the search-path rule of Section 7.14.

The insertion order in the example: 55, 63, 31, 17, 22, 40. So 55 is the root; 63 goes right of 55; 31 goes left of 55; 17 goes left of 31; 22 goes right of 17; 40 goes right of 31.

Most students picked the wrong option — one of the distractors showed 31 and 40 sitting in the right subtree of 55. The instructor's correction: 31 and 40 are smaller than 55, so they can never appear on the right-hand side of 55. The classic mistake — flagged explicitly — is checking only the immediate parent instead of all ancestors. You should not check only the immediate element: a BST requires every left-subtree key to be smaller than the node and every right-subtree key to be larger, against all ancestors, not just the parent. 40 is larger than 31 (its parent) and could sit right of 31 — but it still sits inside the left subtree of 55, which is illegal.

7.19.2 The Correct Tree

       55
      /  \
     31   63
    /  \
   17  40
     \
     22

7.19.3 Visual Intuition — The Global Fence

Picture the root 55 as a fence: everything planted to its left must stay on the left side of the fence, everything to its right on the right side — no exceptions, no matter how deep. The distractor's picture shows 31 and 40 planted on the right of the fence: locally 40 is happy right of 31, but globally it crossed the fence. The visual landmark is the deepest leaf of a subtree: it must still respect the fence at the top. The one-sentence takeaway: in a BST, every node obeys not its parent but its whole ancestry — the tree is a stack of fences, and the top fence is the strictest one.

7.19.4 Common Pitfalls

7.19.5 Student Questions and Answers

Real-world connection: this exam question models a real correctness requirement: when a database or application reconstructs a BST (for example, rebuilding an ordered index from a sorted log of inserts), the reconstruction is trustworthy only if every node passes the full-ancestor check. The distractor's flaw — a locally fine placement that violates a distant ancestor — is the same class of bug that slips into hand-written tree code and breaks range queries later.

7.20 The Least Common Ancestor in a BST

7.20.1 The Idea

Given a BST and two values $n_1$ and $n_2$, the least common ancestor (LCA) is the lowest (deepest) node that is an ancestor of both. A node counts as its own ancestor. In a BST the LCA can be found by a single downward walk: at each node, if both values are smaller than the node, both are in its left subtree; if both are larger, both are in its right subtree; the first node where the two values split — one on each side, or one equal to the node — is the LCA.

7.20.2 Worked Examples

       20
      /  \
     8    22
      \
       12
      /  \
     10  14

7.20.3 Assumptions and Scope

7.20.4 Visual Intuition — The Fork in Two Paths

Picture two ants walking from the root toward keys 10 and 14. For a while they follow the same branches — 20, then 8 — until they reach 12, where one ant turns left and the other turns right: the fork in the road is the LCA. The landmark is the first fork: any common ancestor above the fork (8, 20) also covers both ants, but the fork is the deepest place that does. When one ant's target is on the fork itself (LCA(14, 8)), the fork is simply that node. The takeaway: trace the shared path; the LCA is where the shared path ends.

7.20.5 Common Pitfalls

7.20.6 Student Questions and Answers

Real-world connection: LCA queries are a workhorse of tree algorithms beyond exams — they power "nearest common ancestor" computations in phylogenetic trees (biology), in file-system diff tools (two branches of a directory tree), and in version-control merge-base computations, where the LCA of two commit histories decides the common ancestor commit to merge from. The BST version's single downward walk is the model for these tree algorithms: follow the structure, stop at the fork.

7.21 Past Paper Walkthrough

The instructor opened a past exam paper and walked through its questions, item by item, to show the exam's shape. Several of these are scenario-based — the paper in question was set for an offline closed-book sitting, and the same skills appear in the current (online) format with different framing.

7.21.1 Choosing between Two Algorithms for Small Inputs

The first question: you are given two algorithms for solving a problem of size at most 7. Algorithm one takes $n^2$ steps; algorithm two takes $2^n/4$ steps. Which algorithm do you choose, and why?

The trap: everybody tries $n^2$ and ends up with zero marks — because for $n\le 7$, the computation goes the other way. Compute the actual numbers:

$$n^2=7^2=49\text{steps for algorithm one}$$

$$\frac{2^n}{4}=\frac{2^7}{4}=\frac{128}{4}=32\text{steps for algorithm two}$$

The conceptual point is the one from the asymptotic-notation discussion: asymptotic claims hold for large values of n. For small values of $n$, $n^2$ can be larger than $2^n/4$ — the ordering of the functions flips in the small-n regime. The instructor's warning: this is one of those small things you will miss if you apply the asymptotic intuition mechanically. The solution document itself reads "2n by 4" in shorthand — do not confuse that with $2n/4$; the intended function is $2^n/4$, which for $n=7$ gives 32.

7.21.2 Open Addressing with Three-Slot Buckets

The next question: insert data into a hash table implemented using the open addressing technique. The question states explicitly: apply linear probing for collision resolution, gives the hash function, and says to assume the buckets have 3 slots each. The instructor's note: there is nothing tricky — you can do it easily; only there will be some calculations. The "3 slots each" variant just means each bucket cell can hold up to three entries before probing moves on; the linear-probing mechanics from Section 7.5 apply.

7.21.3 Reconstructing a Tree from Two Traversals

The paper includes: find the pre-order traversal of a binary tree given the in-order and post-order traversals. The instructor's commitment on this topic: one question from "construct the tree given any two traversals" is compulsory — that question is already worth 3 marks, and nobody should lose marks on it. Sometimes the variant asks to construct a full binary tree given post-order and pre-order alone, without in-order. The method was covered in detail in the previous session: given two traversals, find the tree and then find the third traversal — follow that method exactly, or you will not be able to solve it.

7.21.4 Max Heap Insertion and Counting Swaps

The paper asks: consider the following array of a max heap; insert 95 into the array. Questions: how many swaps are required? (explain the swaps). And: give the final array after insertion.

The instructor's advice: first construct the max heap — you need to construct it (or, if you are very confident, you can work in the array directly; showing it in the array is the best thing). The key warning: read the question carefully — it asks for the final array after insertion. Students routinely hand in just the final heap, and that costs marks (two marks were mentioned as cut). Deliver exactly what is asked: the final array.

7.21.5 The Circular Queue Size Formula

A queue is set up in a circular array with front and rear defined as usual, and $n-1$ locations of the array are available for storing elements. Give a formula for the number of elements in the queue in terms of rear, front, and $n$. The answer, discussed fully in class:

$$(n-f+r)\mathrm{mod}n$$

where $f$ is the front index, $r$ is the rear index, and $n$ is the array capacity. The instructor noted this was asked in a closed-book offline paper; in the online format, questions are posed as scenarios so that a direct web search does not hand over the solution.

7.21.6 Array-Based Queue Resizing

An array-based queue throws an exception when the array's capacity has been reached. Suppose we use a resize method to expand the array each time it is full; the cost of a resize that makes the array larger is proportional to the new size. Two cases are asked about: (a) we expand the array's capacity by one element each time — analyze the running time; (b) we double the array's capacity each time — analyze the time complexity.

This was discussed completely in class. Expanding by one costs $O(\text{new size})$ per resize, and doing that for $n$ insertions sums to about $1+2+\cdots +n=O(n^2)$ total work, i.e. $O(n)$ amortized per insertion. Doubling the capacity makes the total work $O(n)$ (each element is copied at most logarithmically many times), i.e. $O(1)$ amortized per insertion.

This is the standard dynamic-array analysis; the same argument applies to the hash table's doubling-and-rehash growth from Section 7.3 — doubling makes growth cheap on average, growing by one makes it expensive.

7.21.7 The Stock Span Problem

A scenario-based question: oil marketing companies have decided to perform an analysis on crude oil prices for $n$ number of days. The aim is to find, for every day, the number of days in a row preceding the present day when the price of the crude oil was not greater than the price on the present day. Describe a linear-time algorithm to solve this using a stack.

This is the stock span problem from the stack material, present in the course slides. The instructor's note: there is a very simple catch — it is just manipulation of indices in a stack; the solution is very small. The difficulty is understanding the question, not writing the solution.

7.21.8 Common Pitfalls

7.21.9 Student Questions and Answers

Real-world connection: every question in this walkthrough maps to a real system — resizing rules are how dynamic arrays and hash tables grow in production, the stock-span stack is the same monotonic-stack technique used in financial analytics for rolling highs and lows, and heap insertion with swap counting is the core of every priority queue in schedulers and event loops.

Exam Guidance Summary

Exam shape (stated by the instructor): there will be one heap question, hashing questions (a hash question was called "100% sure" — expect an open-addressing insertion), definitely one stack or queue question, and one question asking you to write an algorithm. One question from "construct the tree given any two traversals" is compulsory — worth about 3 marks — and the instructor said nobody should lose marks on it. The final paper is fixed by a syllabus committee: the instructor submits questions, but the paper must cover the assigned topics and cannot be biased; if a paper omits topics the committee rejects it. Papers also get tweaked per company collaboration for other cohorts, so the exact phrasing of a past paper may differ from yours — don't argue "it was asked this way" later; the concepts are what matter.

Question types and patterns:

• Expect a hashing question using open addressing with a specified collision method (e.g., linear probing), a given hash function, and possibly a twist like buckets with 3 slots each. If a probing formula is not specified for quadratic probing, either $H(K)+i^2$ or $H(K)+i+i^2$ is acceptable — but be consistent.
• For double hashing, both hash functions are given in the question; if the second one is not given, use $H^{\prime }(K)=Q-(K\mathrm{mod}Q)$ with $Q$ prime.
• The kth-smallest BST question has appeared in an earlier paper. The question will state whether to trace the algorithm or give the algorithm — deliver exactly that.
• Expect a "which BST is formed by this insertion order" identification question — the trap is checking only the immediate parent instead of all ancestors.
• LCA questions have solutions in the material — work through them; skipping them means failing similar exam questions.
• A heap question (insert a value, count the swaps, give the final array) — construct the heap, read the question carefully, and give exactly what is asked (e.g., the final array, not just the heap).
• The circular queue size formula $(n-f+r)\mathrm{mod}n$ was a past closed-book question — memorize the mechanics, because in the online format the same idea arrives wrapped in a scenario.
• The queue-resize amortized analysis (expand by one vs double) is examinable and was discussed in full in class.
• The stock span problem (crude oil prices, linear-time stack algorithm) is in the slides — a model for how scenario questions work.

Algorithm-writing rules: if asked to write an algorithm, the required complexity will be stated — "write a quadratic time algorithm" or "write a linear time algorithm". If the question demands linear time and you submit a quadratic algorithm, the answer is cancelled and credited zero. The same applies to choosing between algorithms: compute for the given (small) $n$ rather than assuming the asymptotically better function wins.

Content and difficulty notes:

• There is no coding on the exam — no code at all; it is concept-based.
• Time complexity may not be included in the mid-sem paper — the instructor was unsure ("I think I'm not sure"), so do not bet the paper on it, and know the material anyway.
• The master's theorem and the substitution method are in the handout and are in scope — the instructor confirmed they will be there even though they were not discussed during the paper walkthrough.
• Past papers: all the exercise questions in the course material are past exam questions — by now solving all of them means you have effectively solved at least three papers. Try each one yourself first, then check the solution. "Be true to yourself."
• Study references: recorded lectures, the T1, T2, R1, R2 references, and Cormen (CLRS) if you want more depth. Going through the PPTs alone will not be enough.
• Use the array representation of a tree in answers unless the question explicitly asks for the tree representation.
• The load factor default is 0.75 when not given. Rehashing: double the size, rehash all existing elements.
• Regular vs makeup: same complexity when you are given the choice; different when makeup is emergency-only.
• Reading carefully: the heap question is the warning case — most lost marks come from answering a different question than the one asked (final array, not final heap).
• Expected number of probes for open addressing: $1/(1-\alpha )$; worst case for all hashing: $O(n)$. Both worth knowing with the load factor below 1 (preferably 0.75).

Study advice (the instructor's parting words): this was the last class before the exam; the exercises in the material are the best preparation — solve them, then compare with the solutions. The recorded lectures, the reference textbooks, and the exercises together are enough; PPTs alone are not.

Key Industry Applications

Real-world: cloud storage provisioning (Dropbox) — storage is allotted incrementally, roughly half of what you request at first; when usage reaches about 75% of the allotment, a notification fires and the provider doubles the capacity. This is exactly the hash-table rehashing pattern: grow by doubling at the load factor, rather than paying the full cost up front. The instructor used it to justify why rehashing cost is acceptable compared with allotting complete storage initially.

Real-world: hash function design for strings — real-world hash functions for string keys use polynomial hashing (evaluate the characters as a polynomial), and alternatives like hexadecimal encoding and polynomial encoding were named; the instructor pointed to a web search on Google for "polynomial hashing" as a follow-up. The engineering lesson: pick a hash function that reduces operational complexity for your key type — the lecture's mod-by-length function was only a teaching toy.

Real-world: choosing hash tables vs alternatives in applications — the decision depends on the application: if you can predict the number of incoming elements, a simple hash function with large initial capacity avoids rehashing; otherwise you pay for good hash functions and growth. If a worst case (all keys colliding) is guaranteed by the data, the professional answer is to not use a hash table.

Real-world: crude oil price analysis (stock span) — oil marketing companies analyze daily crude oil prices to find, for each day, how many consecutive preceding days had prices no greater than the current price; a linear-time stack algorithm solves it. This is the model scenario-based exam question and a real analytics task.

Real-world: dictionary implementations — every language's dictionary/associative-array implementation (the session's running example) is a hash table with separate chaining or open addressing, a load-factor-triggered doubling resize, and rehashing on growth.

Real-world: binary search trees — BSTs underpin ordered maps and ordered sets in standard libraries; the search, insert, delete, successor/predecessor, and kth-smallest operations shown here are the exact operations such structures expose, and the skewing warning (sorted insertions → $O(n)$) is the reason balanced variants exist in production.