Master Rule Sheet

⏱️ Costs at a glance

🧮 Formula sheet

🪤 C traps checklist

• sizeof of an array parameter is the size of a pointer (4 on our 32-bit target); sizeof of a real array is the whole array.
• String literals are read-only: char *p = "abc"; p[0] = 'x'; is undefined behavior; char s[] = "abc"; is a writable copy of 4 bytes.
• strlen stops before '\0'; sizeof counts it.
• Short-circuit: in a && b and a || b the right side may never run (its ++ does not happen).
• Modifying a variable twice without sequencing (i = i++ + ++i) is undefined behavior: no fixed output.
• The order in which function arguments are evaluated is unspecified; do not rely on it.
• Signed −1 compared with an unsigned value becomes a huge unsigned number.
• Integer division truncates toward zero; % takes the sign of the left operand.
• Unparenthesized macros expand textually: SQ(x) x * x gives SQ(2 + 3) = 11.
• A static local is initialised once and keeps its value between calls (and across recursive calls).
• C passes arguments by value; changing a pointer parameter does not change the caller’s pointer — only *p = … reaches the caller.
• Returning the address of a local variable gives a dangling pointer.
• a[i] == *(a + i) == i[a]; pointer arithmetic scales by the element size; pointer difference counts elements.
• Structure size includes padding: members are aligned to their size (char 1, int 4 here).
• switch falls through until break.
• A stray semicolon after for (...) or if (...) makes an empty body.
• Precedence: + binds tighter than <<; == binds tighter than &.
• Freed memory must not be used again; freeing twice is undefined behavior.

🗂️ All rule cards

🧭 Phase 0 — Foundations

0.1.1 Programs and instructions; source code → compiler → executable; the shape of a first C program (main, printf, return)

• Program = list of instructions; processor runs machine code (0s and 1s).
• Source code (.c) → compiler → executable. Rule broken → compile-time error, nothing runs.
• Shape: #include <stdio.h> · int main(void) { … return 0; }.
• Statements run top to bottom; each ends with ;.
• printf("…") prints exactly the string literal; it never adds a new line.
• Escapes (one character each): \n new line, \t tab, \\ backslash, \" quote.
• Comments: /* … */ (not nestable) and // …; inside quotes they are plain text.

0.1.2 Memory as numbered boxes: bits, bytes, addresses; a variable as a named box

• bit = 0 or 1; byte = 8 bits; n bits → patterns double with each bit (8 bits → 256).
• Memory = numbered one-byte boxes; number = address; multi-byte value’s address = its first byte.
• int = whole number, 4 bytes here; int x = 5; creates and fills a box.
• x = expr; evaluate right side with current values, then overwrite x.
• Unfilled local variable = unpredictable value.
• %d in printf = placeholder for the next value, as a whole number.
• Identifier: letters, digits, _; not starting with a digit; not a keyword; case-sensitive.
• Swap needs a third variable: t = a; a = b; b = t;

0.2.1 Powers of 2 and logarithms; floor and ceiling

• 2^10^ = 1024 (K), 2^20^ ≈ 10^6^ (M), 2^30^ ≈ 10^9^ (G).
• 2^a^·2^b^ = 2^a+b^; 2^a^/2^b^ = 2^a−b^; (2^a^)^b^ = 2^ab^.
• log₂ x = the power of 2 that gives x; log₂ 1 = 0.
• log(ab) = log a + log b; log(a^k^) = k log a; logb x = log₂ x / log₂ b.
• ⌊x⌋ round down, ⌈x⌉ round up; ⌈a/b⌉ = ⌊(a + b − 1)/b⌋ for positive whole a, b.
• Halvings from n to 1 = ⌊log₂ n⌋; doublings from 1 to ≥ n = ⌈log₂ n⌉; bits for n labels = ⌈log₂ n⌉.

0.2.2 Sums of series (1+2+…+n, 1+2+4+…+2ⁿ); basic counting

• Σ i (i = 1 to n) = n(n + 1)/2; 1 + … + (n − 1) = n(n − 1)/2.
• a + … + b = (b − a + 1)(a + b)/2.
• Σ i² = n(n + 1)(2n + 1)/6.
• 1 + 2 + … + 2^n^ = 2^n+1^ − 1; 1 + r + … + r^n^ = (r^n+1^ − 1)/(r − 1).
• n + n/2 + n/4 + … < 2n.
• Sum rule (or) add; product rule (and then) multiply.
• n! orders; ordered k of n: n!/(n − k)!; unordered: nCr = n!/(k!(n − k)!); pairs nC2; subsets 2^n^.

💻 Phase 1 — Programming in C

1.1.1 Data types and their sizes; signed vs unsigned; constants; variables; declaration vs definition

• Sizes here: char 1, short 2, int 4, long 4, long long 8, float 4, double 8; only char = 1 is guaranteed.
• n bits: unsigned 0 … 2ⁿ − 1; signed −2ⁿ⁻¹ … 2ⁿ⁻¹ − 1.
• sizeof = size in bytes, an operator; print with %u (or %zu).
• Literals: 42, 42u, 42L, 3.75 (double), 3.75f, 'A' = 65, 0x.. hex, 0.. octal.
• const variables cannot be assigned again.
• Declaration = name + type; definition = declaration + memory. Defined once, declared many times.

1.1.2 Operators: arithmetic, relational, logical with short-circuiting, bitwise, assignment, ++ and --; precedence and associativity; undefined behavior

• int / int truncates towards 0; a % b has the sign of a; (a/b)*b + a%b == a.
• Relational and logical results are int 1 or 0; non-zero = true.
• && and || short-circuit: right side may never run (side effects skipped).
• Bitwise: & | ^ ~ << >>; ~x = −x − 1; x<<k = x·2ᵏ; x>>k = ⌊x/2ᵏ⌋ for x ≥ 0.
• x++ old value then add; ++x add then new value.
• Precedence: unary > * / % > + − > shifts > relational > == != > & > ^ > | > && > || > ?: > = > ,
• Unary, ?: and assignment associate right to left; others left to right.
• Changing a variable twice (or change + read) in one expression without an ordering point = undefined behavior.

1.1.3 Type conversion: implicit promotion, casting, overflow, char as a small integer; what printf returns

• char/short → int in arithmetic (integer promotion).
• Mixed types: convert towards double; same-size signed + unsigned → unsigned.
• double → int drops the fraction (towards 0); big int → char keeps low 8 bits.
• Cast (type)e converts e only: (double)a/b ≠ (double)(a/b).
• Unsigned wraps mod 2ⁿ; signed overflow is undefined.
• char arithmetic: 'A' = 65, 'a' = 97, '0' = 48; 'd' − '0' = digit value.
• printf returns characters printed; sizeof does not evaluate its operand; never compare fractions with ==.

1.2.1 if / else if / else; nested conditions; switch and fall-through

• if (cond) S1; else S2; — cond non-zero → S1.
• Braces group statements; without them one statement belongs to the if.
• else ladder: first true branch runs, rest skipped.
• Dangling else binds to the nearest unmatched if.
• switch: evaluate once, jump to matching case/default, run down until break or }.
• Case labels: distinct integer constants (chars allowed).
• if (x = 5) assigns; compare with ==.

1.2.2 for, while, do-while; break and continue; tracing loop output and counting iterations

• while: test then body; do-while: body then test (≥ 1 run); for (init; test; update).
• for ≡ init; while (test) { body; update; }
• break leaves the innermost loop/switch; continue skips to update (for) or test (while).
• i = a..b−1 step s: ⌈(b − a)/s⌉ runs; i *= 2 up to n: ⌊log₂ n⌋ + 1 runs.
• Nested dependent loops: add the series (n(n + 1)/2, 2ᵏ⁺¹ − 1 …).
• Stray ; after for/while = empty body; while (n--) ends with n = −1.

1.3.1 Declaring, defining, calling; parameters; return values; call by value

• type name(params) { … return v; } — void when nothing is returned.
• Call: evaluate args → copy into params → run → value replaces the call.
• Prototype (declaration) before first use; definition = body.
• Call by value only: parameters are copies; caller’s variables unchanged.
• return ends the function immediately.
• Argument evaluation order is unspecified.

1.3.2 Scope vs lifetime; local, global, static, extern, register; shadowing in blocks; static local variables

• Scope = where a name is visible; lifetime = when its memory exists.
• Local/auto: block scope, born and destroyed with the block, garbage start.
• Global: file scope (extern elsewhere), whole run, starts at 0.
• static local: block scope, whole run, initialized once (0 default), keeps value.
• static global/function: this file only. extern: declaration, not definition.
• Inner declarations shadow outer ones inside their block only.
• register: hint; its address may not be taken.

1.3.3 How calls work: the call stack and stack frames

• Call stack: push a frame per call, pop on return; last in, first out.
• Frame = parameters + automatic locals + return address + saved bookkeeping.
• Locals vanish with their frame; statics/globals live outside the stack.
• Depth = frames at one moment; total calls can exceed depth.
• Too deep → stack overflow.

1.4.1 & and *; pointer declaration; NULL; pointer to pointer

• &x = address of x; int *p = &x; p points to x.
• *p in an expression is the variable p points to (read or write).
• Declaration star belongs to one name: int *p, q; → q is int.
• All pointers have the same size (4 here, 8 on 64-bit).
• NULL = points to nothing; dereferencing NULL/garbage = undefined.
• int **q = &p; *q is p; **q is *p.

1.4.2 Simulating call by reference with pointers (swap)

• Simulated call by reference: param type T *, call with &var, use *param.
• Pointer parameters return extra results.
• The pointer parameter itself is a copy: p = q inside does not affect the caller.
• Change the caller’s pointer via T ** (pass &p).
• Same address passed twice → parameters alias one variable.

1.4.3 Pointer arithmetic and why it scales by type size

• p + k = address + k × sizeof(*p); p++ moves one element.
• q − p = number of elements between (same row).
• Allowed: ptr ± int, ptr − ptr, comparisons. Not: ptr + ptr, ×, ÷.
• *p++ = *(p++); *++p = *(++p); ++*p = ++(*p); (*p)++ changes the value, p stays.
• One past the end may be computed/compared, never dereferenced.

1.5.1 1-D arrays; a[i] == *(a+i) == i[a]; arrays decaying to pointers; passing arrays to functions; the sizeof trap

• int a[n]: indices 0 … n−1; element i at base + i·w.
• Partial initializer zero-fills; int a[] = {…} sizes itself.
• a[i] ≡ *(a + i) ≡ i[a]; p[i] works for any pointer.
• a decays to &a[0] except in sizeof a and &a (whole array).
• Array parameter = pointer: sizeof gives 4 here; pass the length.
• Out-of-range index = undefined; arrays cannot be assigned.

1.5.2 2-D arrays; row-major layout; pointer to array vs array of pointers; reading complex declarations

• T a[R][C]: &a[i][j] = B + (i·C + j)·w (row-major).
• a[i][j] ≡ ((a + i) + j) ≡ *(a[i] + j).
• a decays to T (*)[C]; a + 1 jumps a row; a[i] + 1 jumps an element.
• Parameter: int m[][C] or int (*m)[C] — columns required.
• int *p[N] array of pointers; int (*p)[N] pointer to array.
• Read declarations: name → right ([] , ()) → left (*), parentheses first.

1.5.3 Strings: char arrays, '\0', read-only string literals, strlen vs sizeof, string functions and tracing string code

• String = chars + '\0'; "abc" takes 4 bytes.
• char s[] = "…" writable copy; char *p = "…" points to a read-only literal.
• strlen counts before \0; sizeof counts the whole array (or 4 for a pointer).
• strcpy, strcat, strcmp (0, 0, >0), strncpy in string.h; compare with strcmp, not ==.
• %s prints from a pointer up to \0; p + k prints the tail.
• *p + 1 ≠ *(p + 1).

1.6 Structures, unions, typedef; self-referential structures; structure size and padding

• struct T { members }; access s.m or p->m ≡ (*p).m.
• Struct assignment and argument passing copy all members.
• typedef gives a type a new name.
• Self-referential: struct T { …; struct T *next; } (pointer only).
• Padding: member at multiple of its size; total multiple of largest member.
• union: members overlap; size = largest member rounded for alignment.

1.7 Dynamic memory: malloc, calloc, realloc, free; stack vs heap; dangling pointers, memory leaks, double free

• Regions: code, static data, heap (malloc), stack (frames).
• malloc(n) garbage; calloc(k, s) zeroed; realloc(p, n) may move; free(p).
• Use n * sizeof(T); check NULL; use realloc’s result.
• Heap lives until free; stack locals die on return.
• Dangling: using freed/popped memory. Leak: losing the last pointer. Double free: freeing twice. All undefined or wasteful.
• After free(p), set p = NULL.

1.8 Preprocessor macros and their expansion traps; function pointers

• Preprocessor runs before compiling: #include, #define, #ifdef.
• #define is text substitution: expand fully, then apply precedence.
• Bracket parameters and the whole body: #define SQ(x) ((x) * (x)).
• Side-effect arguments may be evaluated several times (undefined for ++).
• int (*f)(int, int) = add; f(2, 3) or (*f)(2, 3).
• Function pointer arrays and callbacks; int *f(int) is different.

🔁 Phase 2 — Recursion

2.1.1 Base case and recursive case; tracing calls on the stack

• Recursive function = base case (no call) + recursive case (smaller input).
• Every input must eventually reach a base case, or the stack overflows.
• Each call has its own frame: own parameters and locals.
• Calls go down to the base case; results come back up.
• Depth = longest chain of active calls (sum(n): n + 1).

2.1.2 Recursion trees; counting calls; work done before vs after the recursive call

• Before the call: runs going down (call order). After the call: runs coming back (reverse order).
• Recursion tree: one box per call; base cases at the bottom; top = first call.
• Calls with two branches: C(n) = 1 + C(left) + C(right); fill a table bottom-up.
• fib calls: 1, 1, 3, 5, 9, 15, 25, 41 for n = 0…7.
• Two calls of n − 1 each: 2ⁿ − 1 prints; depth n.

2.1.3 Classic patterns: factorial, Fibonacci, GCD, power, Tower of Hanoi (2ⁿ−1 moves), digit/array recursion

• n! = n·(n − 1)!, 0! = 1: n calls.
• fib(n) = fib(n − 1) + fib(n − 2): exponential calls; loop is linear.
• gcd(a, b) = gcd(b, a % b), gcd(a, 0) = a.
• xⁿ by halving: ≈ log₂ n calls.
• Hanoi: M(n) = 2M(n − 1) + 1 = 2ⁿ − 1; largest disk 1 move, smallest 2ⁿ⁻¹.
• Digits: n % 10 last digit, n / 10 rest. Arrays: a[n − 1] + rest, or *a + (a + 1).

2.1.4 Computing what a recursive function returns via its recurrence; static and global variables inside recursion

• Write the recurrence: f(n) in terms of f(smaller) + base values copied exactly from the code.
• Pure functions: fill a table bottom-up.
• Known forms: f(n − 1) + n → n(n + 1)/2; 2f(n − 1) + 1 → 2ⁿ − 1; f(n/2) + 1 → ⌊log₂ n⌋ + 1.
• Static/global inside recursion: shared by all calls, initialized once; trace calls in execution order.
• return f(…) passes the base-case value up unchanged.

2.2 Counting work: a Big-O primer

• Count basic steps; keep the dominant term; drop constants.
• O = upper bound, Ω = lower bound, Θ = exact growth.
• Sequence adds; nesting multiplies; halving/doubling loop = O(log n).
• 1 log n √n n n log n n² n³ 2ⁿ n!
• Recursion: (number of calls) × (work per call); stack space = depth.
• Default = worst case.

📚 Phase 3 — Linear Data Structures

3.1 Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and search

• ADT = operations + behaviour; data structure = an implementation.
• Array: access O(1); insert/delete at p O(n − p); search O(n), sorted O(log n).
• Row-major: B + ((i − l₁)·n₂ + (j − l₂))·w; column-major: B + ((j − l₂)·n₁ + (i − l₁))·w.
• nₖ = uₖ − lₖ + 1; 3-D row-major: B + (i·n₂n₃ + j·n₃ + k)·w (from 0).
• Binary search: sorted only; ⌊log₂ n⌋ + 1 probes.

3.2.1 Stack ADT; push/pop/peek; array implementation; overflow and underflow

• Stack = LIFO: push, pop, peek, isEmpty, isFull — all O(1).
• Array version: top = −1 empty; st[++top] = x; return st[top--]; full when top == MAX − 1.
• Overflow: push when full; underflow: pop/peek when empty.
• Uses: call stack, undo, bracket matching, expression evaluation, backtracking.

3.2.2 Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluation

• Brackets: push openers; closer must match the top; empty at the end.
• Postfix: operand → output; ( push; ) pop to (; operator pops higher (or equal, if left-assoc) then pushes; end pops all.
• Precedence ^ > * / % > + −; ^ right-associative.
• Prefix: reverse, swap brackets, convert, reverse — or place operators before their operands from inside out.
• Evaluate postfix: operand push; operator pops right then left, pushes result.

3.2.3 Valid stack permutations; Catalan numbers

• Stack permutation: fixed input order, choose when to push/pop.
• Test by simulation, or forbid x … y … z with y z x.
• Catalan C(n) = (2n)!/((n + 1)!·n!) = (2n choose n)/(n + 1).
• C(0…7) = 1, 1, 2, 5, 14, 42, 132, 429.
• Also counts balanced bracket strings and push/pop sequences.

3.3.1 Queue ADT; linear array queue and its wasted-space problem

• Queue = FIFO: enqueue at rear, dequeue at front.
• Linear array: front = 0, rear = −1; q[++rear] = x; q[front++]; empty front > rear; full rear == MAX − 1.
• Items = rear − front + 1.
• Problem: slots before front are wasted; the next lesson bends the array into a ring.

3.3.2 Circular queue: full/empty conditions and index arithmetic

• Advance: i = (i + 1) % N.
• Standard: front = rear = 0 start; enqueue rear = (rear+1)%N; dequeue front = (front+1)%N.
• Empty: front == rear; full: (rear + 1) % N == front; capacity N − 1.
• Items: (rear − front + N) % N.
• Counter variant: full count == N, empty count == 0.

3.3.3 Deque; priority queue as a concept; queue from two stacks and stack from two queues (operation costs)

• Deque: insert/delete at both ends, O(1); input-/output-restricted variants.
• Priority queue: delete highest priority; unsorted O(1)/O(n), sorted O(n)/O(1); Phase 5 gives O(log n)/O(log n).
• Queue from 2 stacks: enqueue push(in); dequeue pop(out), pour in → out only when out empty; O(1) amortized.
• Stack from 2 queues: push O(1), pop O(n) (or the reverse).

3.4.1 Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletion

• Node = data + next; head → first node; last->next = NULL; empty: head == NULL.
• Traverse: for (p = head; p; p = p->next) — O(n).
• Insert after p: n->next = p->next; p->next = n; (in this order).
• Insert at head O(1); at tail O(n) (O(1) with tail pointer).
• Delete: prev->next = cur->next; free(cur); first node changes head.
• Head-changing functions take struct node ** or return the head.

3.4.2 Reversing a list (iterative and recursive); finding the middle; detecting a cycle (fast/slow pointers)

• Reverse: while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return prev;
• Recursive: rest = rrev(head->next); head->next->next = head; head->next = NULL;
• Middle: slow +1, fast +2 while fast && fast->next; even n → second middle.
• Cycle: slow == fast ⇒ cycle; fast hits NULL ⇒ none. O(n) time, O(1) space.

3.4.3 Doubly and circular linked lists; operation costs compared with arrays

• Doubly linked: prev + next; delete/insert beside a known node O(1); 4 writes to insert, 2 to delete.
• Circular: last->next = head; traverse with do-while until back at the start.
• A last pointer on a circular list gives O(1) access to both ends.
• Singly linked + tail: insert at end O(1), delete at end O(n).
• Price of doubly linked: one more pointer per node.

3.4.4 Stack and queue built on linked lists

• Linked stack: top = head; push/pop at head; empty top == NULL.
• Linked queue: front = head (delete), rear = last (insert); both O(1).
• Empty enqueue sets front = rear = n; last dequeue sets rear = NULL.
• No fixed capacity; extra pointer per item; malloc/free per operation.

3.4.5 GATE drill: tracing pointer-manipulation code on linked lists

• Draw boxes + arrows; label pointer variables; one change per statement.
• p->next = p->next->next unlinks one node.
• q one step behind p reaches the second-to-last node.
• Data swap vs link swap: same printout, different nodes.
• Recursion over a list: before-call prints forwards, after-call backwards; p->next->next skips alternate nodes.

🌳 Phase 4 — Trees & Binary Search Trees

4.1 Tree vocabulary: root, parent, child, sibling, leaf, internal node, degree, level, depth, height; the edges-vs-nodes convention

• Tree: one root, every other node has exactly one parent, no loops; n nodes → n − 1 edges.
• parent/child/sibling; ancestor/descendant; leaf (no children) vs internal; subtree; forest.
• Degree of node = number of children; degree of tree = maximum.
• Depth = edges from root; level = depth (root 0 here); height = edges to the deepest leaf; empty tree −1.
• Nodes convention adds 1 to every height/level: always state it.

4.2.1 Strict/full, complete and perfect binary trees

• Binary tree: each node has a left and a right subtree (possibly empty); left ≠ right.
• Strict/full: every node 0 or 2 children (some books: full = perfect).
• Complete: all levels full except the last, which is left-packed.
• Perfect: all levels full (strict + complete).
• Skewed: one child per node; height n − 1.

4.2.2 Binary tree properties: nodes per level and height; n₀ = n₂ + 1; minimum and maximum height

• Level i: ≤ 2ⁱ nodes; height h: h + 1 ≤ n ≤ 2ʰ⁺¹ − 1 (edges).
• n nodes: ⌊log₂ n⌋ ≤ height ≤ n − 1.
• n₀ = n₂ + 1; strict tree with i internal nodes: i + 1 leaves, 2i + 1 nodes.
• n + 1 NULL pointers.
• Nodes convention: replace h by h − 1.

4.2.3 Representations: linked nodes vs array indexing (both 0-based and 1-based formulas)

• Linked: struct tnode { data; *left; *right; }; empty subtree = NULL.
• 0-based: children 2i+1, 2i+2; parent ⌊(i−1)/2⌋.
• 1-based: children 2i, 2i+1; parent ⌊i/2⌋.
• Array form compact only for complete trees; height h may need 2ʰ⁺¹ − 1 slots.
• Heaps use arrays; search trees use links.

4.3.1 Preorder, inorder, postorder (recursive code and hand tracing)

• Preorder: root, L, R. Inorder: L, root, R. Postorder: L, R, root.
• Euler walk: 1st touch pre, 2nd in, 3rd post.
• O(n) time; depth = height + 1.
• Read mixed traversals statement by statement (before/between/after calls).

4.3.2 Level-order traversal using a queue

• Level order: enqueue root; repeat: dequeue, print, enqueue left then right.
• O(n) time; queue holds at most about one level (≤ n/2 for complete trees).
• Stack → branch-first; queue → level order.
• Separate levels by recording the queue size; height = levels − 1.
• Array without holes: level order = index order.

4.3.3 Rebuilding a tree from two traversals; counting distinct binary trees (Catalan)

• Pre + in or post + in or level + in → unique tree; pre + post only for strict trees.
• Root: first of pre, last of post; inorder splits left/right.
• Shapes with n nodes: Catalan C(n) = (2n choose n)/(n + 1).
• Labelled binary trees: n!·C(n); trees with a fixed preorder: C(n).

4.4 Recursive code on trees: count nodes, leaves, height, mirror, sums; expression trees

• Recursive pattern: P(NULL) base; P(t) from P(left), P(right) and t.
• count = 1 + L + R; leaves = 1 at a leaf else L + R; height = 1 + max(L, R) with −1 for NULL; sum = data + L + R.
• O(n) time, O(height) stack.
• Mirror: swap children at every node; mirrored inorder = reversed inorder.
• Expression tree: operators inside, operands at leaves; postorder evaluates; traversals give postfix/prefix/infix.

4.5.1 The BST property; search, minimum, maximum; inorder gives sorted order

• BST: all keys in left subtree node all keys in right subtree, for every node.
• Search: compare, go left/right; O(h).
• Min = leftmost; max = rightmost; O(h).
• Inorder of a BST is sorted (and only BSTs have sorted inorder).
• Successor = min of right subtree (if any).

4.5.2 BST insertion; building a BST from an insertion sequence; best- vs worst-case height

• Insert: search; attach a new leaf at the NULL reached; O(h).
• First key = root; shape depends on insertion order.
• Best height ≈ ⌊log₂ n⌋; worst n − 1 (sorted input).
• Building from n keys: O(n log n) balanced, O(n²) worst; sorted input costs n(n − 1)/2 comparisons.

4.5.3 BST deletion: leaf, one child, two children (inorder successor or predecessor)

• Leaf: remove. One child: splice the child up.
• Two children: copy the inorder successor (min of right subtree) or predecessor (max of left), then delete that node (0 or 1 child).
• Successor and predecessor give different valid BSTs.
• O(h).

4.5.4 BST GATE drills: BST from a preorder/postorder sequence; number of BSTs; valid search paths; insertion orders giving the same BST

• BST from preorder: insert in preorder; from postorder: insert in reverse postorder.
• Inorder of a BST = sorted keys.
• Number of BSTs on n keys = C(n).
• Search path valid iff each key lies inside the interval set by earlier left/right moves.
• Insertion orders giving T: C(L + R, L) × orders(left) × orders(right).
• k-th smallest: k-th node of inorder.

4.6 Balanced BSTs — AVL idea, balance factor, rotations, minimum nodes for a given height

• AVL: every node’s balance factor h(L) − h(R) ∈ {−1, 0, +1}.
• LL → right rotation; RR → left rotation; LR → left then right; RL → right then left.
• Rotations keep inorder, fix height, cost O(1).
• Min nodes: N(0) = 1, N(1) = 2, N(h) = N(h−1) + N(h−2) + 1 (1, 2, 4, 7, 12, 20, 33).
• Height ≈ ≤ 1.44 log₂ n; all operations O(log n).

⛰️ Phase 5 — Binary Heaps

5.1 The heap idea: a complete binary tree in an array; max-heap and min-heap

• Heap = complete binary tree + heap order (max: parent ≥ children; min: parent ≤ children).
• 0-based: children 2i + 1, 2i + 2; parent ⌊(i − 1)/2⌋. 1-based: 2i, 2i + 1; ⌊i/2⌋.
• Leaves: last n − ⌊n/2⌋ positions; height ⌊log₂ n⌋.
• Max at root O(1); min among leaves O(n); search O(n).

5.2 Heap insertion (sift-up) and deleting the root (sift-down)

• Insert: place at index n; sift-up (swap with parent while larger); ≤ h comparisons.
• Delete max: root ← last; n−−; sift-down (swap with larger child while smaller); ≤ 2h comparisons.
• Both O(log n).
• Increase key → sift-up; decrease key → sift-down (max-heap).

5.3 Build-heap in O(n) vs n insertions; heap sort

• Build-heap: for i = ⌊n/2⌋ − 1 down to 0, sift-down(i); O(n).
• n inserts: O(n log n) worst case; may give a different heap.
• Heap sort: build, then n − 1 × (swap root with last, shrink, sift-down); O(n log n), in place, not stable.
• Merging two heaps: concatenate + build: O(n).

5.4 Heap GATE drills: k-th largest, number of heaps, comparisons, d-ary heaps

• k-th largest (distinct keys) at depth ≤ k − 1; 2nd largest at index 1 or 2; k-th found in O(k log n).
• H(n) = C(n − 1, L)·H(L)·H(n − 1 − L): 1, 1, 2, 3, 8, 20, 80.
• Insert ≤ h, delete ≤ 2h comparisons; find-min O(n).
• d-ary (0-based): children d·i + 1 … d·i + d; parent ⌊(i − 1)/d⌋; height ≈ log_d n.

🕸️ Phase 6 — Graphs

6.1 Graph vocabulary

• G = (V, E); undirected / directed; weighted; simple = no loops, no parallel edges.
• Σ deg = 2e; odd-degree vertices even in number; directed: Σ in = Σ out = e.
• Max edges: n(n − 1)/2 undirected, n(n − 1) directed; graphs on n labelled vertices: 2^(n(n−1)/2).
• Connected ⇒ e ≥ n − 1; k components ⇒ e ≥ n − k; max with k components (n − k)(n − k + 1)/2.
• Tree: connected, acyclic, n − 1 edges; forest: n − k edges; DAG: no directed cycle.

6.2 Graph representations: adjacency matrix, adjacency list, incidence matrix

• Matrix: n × n, Θ(n²) space, O(1) edge test, Θ(n) neighbour scan; symmetric for undirected; 2e ones.
• Lists: Θ(n + e) space; head insertion reverses input order.
• Incidence: n × e; two 1s per column (undirected).
• (A²)[i][j] = walks of length 2; diagonal = degrees.
• Dense → matrix; sparse → lists.

6.3 Graph traversals: BFS, DFS, connected components

• BFS: queue; mark when enqueued; visits by distance; shortest paths in unweighted graphs.
• DFS: recursion/stack; dives then backtracks; non-parent seen neighbour ⇒ cycle (undirected).
• Components: restart a traversal at each unseen vertex; count the starts.
• Θ(n + e) with lists, Θ(n²) with a matrix.
• Orders depend on neighbour order; check validity by simulation.