This HL-only Topic 5 covers recursion and the classic abstract data structures: stacks and queues, linked lists, and binary (search) trees with their pre-order, in-order and post-order traversals.
Work through each screen, answer the questions as you go (some are wordy, some are calculations) and collect ⭐ stars. Press Start when you are ready.
A recursive subprogram calls itself. It needs a base case that stops the recursion and a recursive case that moves toward it. Each call is stored on the call stack.
factorial(n): base case factorial(1) = 1; recursive case n times factorial(n minus 1). So factorial(6) = 6 times 5 times 4 times 3 times 2 times 1 = 720.
The Fibonacci sequence (starting 1, 1) adds the two previous terms: 1, 1, 2, 3, 5, 8, 13, 21, ... Each term can be defined recursively as fib(n) = fib(n minus 1) + fib(n minus 2).
A stack is last in, first out. Operations: push (add on top), pop (remove from top), peek (look at the top). Stacks are used for the call stack, undo history and expression evaluation.
A queue is first in, first out. Operations: enqueue (add at the rear), dequeue (remove from the front). Queues are used for print spoolers, buffers and scheduling.
Tap an item, then the structure it belongs to.
A linked list is a chain of nodes; each node stores data and a pointer to the next node. Unlike arrays, they grow and shrink dynamically and allow cheap insertion and deletion, but they have no random access — you must follow the pointers.
A binary tree has nodes with up to two children (left and right). In a binary search tree (BST), every left descendant is smaller than the node and every right descendant is larger, giving fast searching.
Insert 50, 30, 70, 20, 40, 60, 80 into a BST: 50 is the root; 30 and 70 are its children; 20 and 40 sit under 30; 60 and 80 under 70.
Tap a traversal on the left, then what it does.
A two-dimensional array stores data in rows and columns, like a grid or table. An element is accessed by two indices, for example grid[row][column]. They model images, boards and spreadsheets.
Different structures suit different jobs. Stack and queue push/pop and enqueue/dequeue are O(1). Searching a balanced binary search tree is O(log n). A linked list must be traversed to find an item, which is O(n), but insertion once positioned is cheap.
Recursion: base case + recursive case; uses the call stack
Stack: LIFO — push, pop, peek
Queue: FIFO — enqueue, dequeue
Linked list: nodes with pointers, dynamic, no random access
BST: left is smaller, right is larger; in-order gives sorted order
Traversals: pre (root,L,R), in (L,root,R), post (L,R,root)
You have covered the whole of HL Topic 5 — abstract data structures. Press Finish to see your score.
You have worked through Abstract data structures. 🎉
Your stars: 0 / 0
Next: test yourself in the Evaluate stage Confidence Quiz, then lock it in with Verify.