Data Structures and Algorithms: From Arrays to Trees

Lesson Promise

By the end of this lesson, you will understand how hash tables resolve collisions, how trees are traversed recursively, and how recursion builds and unwinds a call stack. We trace each structure's execution to show the real memory access patterns behind the abstractions.

Narration Draft

Part 1 — Arrays vs Linked Lists (5:00) Recap: arrays are contiguous, linked lists are scattered. Trace an array insertion showing the O(n) shift. Show how a linked list insertion is O(1) but pays a cache-miss cost per node.

Part 2 — Hash Tables (6:00) A hash table maps keys to values. Show the hash function, the bucket array, and collision resolution via chaining. Trace a hash table lookup: hash(key) → bucket index → walk linked list → find value. Show the average-case O(1) and worst-case O(n).

Part 3 — Recursion and the Call Stack (5:00) Show factorial(5) pushing frames onto the stack, reaching the base case, then unwinding. Emphasize that each frame stores local variables and a return address.

Part 4 — Trees and Recursion (6:00) A binary tree is a recursive data structure: a node has a value and two children, each of which is itself a tree. Trace a recursive tree traversal (inorder): recurse left, visit node, recurse right. Show the call stack growing and shrinking.

Part 5 — Big-O Analysis (2:00) Review how to count operations as a function of input size. Show O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ) with concrete examples.

Visual Sequence

1. Array insertion trace: resize → shift → write
2. Hash table: hash function → bucket array → collision chain
3. Call stack: factorial(5) → factorial(4) → ... → factorial(0) → unwind
4. Binary tree: inorder traversal animation with stack frames
5. Sorting algorithms: O(n log n) vs O(n²) on a graph

Companion Material

• Article: Complexity and Analysis
• Article: Hash Tables
• Trace: Hash Table Lookup
• Article: Trees and Heaps
• Trace: Tree Traversal
• Practice: Two Sum
• Practice: LRU Cache