Computer Science · Cheatsheet
Topic 4 · Abstract Data Structures (HL)
Chapter 2 · Recursion & trees
📋 Reference · always available
Recursion
Calls itself toward a base case: `f(n)=n*f(n-1)`, `f(1)=1`.
Base case
Stops recursion; without it → stack overflow.
Call stack
Calls push (wind up), resolve LIFO (unwind).
Binary tree
≤ 2 children. Root (no parent), leaf (no children).
Traversals
Pre (root,L,R) · In (L,root,R = sorted for BST) · Post (L,R,root).