COMP 2421 Ultimate Cheat Sheet

Binary Tree

AVL Tree

BST Traversal

Inorder:   Left → Root → Right   (sorted order)
Preorder:  Root → Left → Right   (prefix)
Postorder: Left → Right → Root   (postfix)

Collision Resolution

Load Factor & Rehashing

Cursor List (Array-Based LL)

#define MAX 10
int data[MAX], next[MAX], head = -1, freeHead = 0;

void init() {
  for (int i = 0; i < MAX-1; i++) next[i] = i+1;
  next[MAX-1] = -1;
}

int alloc() {
  if (freeHead == -1) return -1;
  int i = freeHead;
  freeHead = next[freeHead];
  return i;
}

void freeNode(int i) {
  next[i] = freeHead;
  freeHead = i;
}

void insertAfter(int val, int prev) {
  int n = alloc();
  if (n == -1) return;
  data[n] = val;
  next[n] = next[prev];
  next[prev] = n;
}

AVL Rotations (LL, RR, LR, RL)

int height(Node* n) {
  return n ? n->h : 0;
}

int bf(Node* n) {
  return n ? height(n->left) - height(n->right) : 0;
}

Node* rotateRight(Node* y) {
  Node* x = y->left;
  Node* T2 = x->right;
  x->right = y;
  y->left = T2;
  y->h = 1 + max(height(y->left), height(y->right));
  x->h = 1 + max(height(x->left), height(x->right));
  return x;
}

Node* rotateLeft(Node* x) {
  Node* y = x->right;
  Node* T2 = y->left;
  y->left = x;
  x->right = T2;
  x->h = 1 + max(height(x->left), height(x->right));
  y->h = 1 + max(height(y->left), height(y->right));
  return y;
}

Node* insertAVL(Node* root, int key) {
  if (!root) return newNode(key);
  if (key < root->data) root->left = insertAVL(root->left, key);
  else if (key > root->data) root->right = insertAVL(root->right, key);
  else return root;
  root->h = 1 + max(height(root->left), height(root->right));
  int b = bf(root);
  // LL
  if (b > 1 && key < root->left->data) return rotateRight(root);
  // RR
  if (b < -1 && key > root->right->data) return rotateLeft(root);
  // LR
  if (b > 1 && key > root->left->data) {
    root->left = rotateLeft(root->left);
    return rotateRight(root);
  }
  // RL
  if (b < -1 && key < root->right->data) {
    root->right = rotateRight(root->right);
    return rotateLeft(root);
  }
  return root;
}

BST Delete — Case 3 (Two Children)

// Find inorder successor (min of right subtree)
Node* minValueNode(Node* node) {
  Node* cur = node;
  while (cur && cur->left) cur = cur->left;
  return cur;
}

Node* deleteNode(Node* root, int key) {
  if (root == NULL) return root;

  if (key < root->data)
    root->left = deleteNode(root->left, key);
  else if (key > root->data)
    root->right = deleteNode(root->right, key);
  else {
    // Case 1 & 2: 0 or 1 child
    if (root->left == NULL) {
      Node* temp = root->right;
      free(root);
      return temp;
    }
    if (root->right == NULL) {
      Node* temp = root->left;
      free(root);
      return temp;
    }
    // Case 3: two children
    Node* temp = minValueNode(root->right);
    root->data = temp->data;
    root->right = deleteNode(root->right, temp->data);
  }
  return root;
}

Circular Queue (Array)

#define MAX 100
typedef struct {
  int items[MAX];
  int front, rear;
} CQueue;

void init(CQueue* q) { q->front = -1; q->rear = -1; }

int isEmpty(CQueue* q) { return q->front == -1; }
int isFull(CQueue* q) {
  return (q->rear + 1) % MAX == q->front;
}

void enqueue(CQueue* q, int val) {
  if (isFull(q)) return;
  if (isEmpty(q)) q->front = 0;
  q->rear = (q->rear + 1) % MAX;
  q->items[q->rear] = val;
}

int dequeue(CQueue* q) {
  if (isEmpty(q)) return -1;
  int val = q->items[q->front];
  if (q->front == q->rear) {
    q->front = -1; q->rear = -1;
  } else {
    q->front = (q->front + 1) % MAX;
  }
  return val;
}

Towers of Hanoi

void hanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    printf("Move disk 1 from %c to %c\n", from, to);
    return;
  }
  hanoi(n-1, from, aux, to);
  printf("Move disk %d from %c to %c\n", n, from, to);
  hanoi(n-1, aux, to, from);
}
// T(n) = 2T(n-1) + 1 = O(2^n)

SumTree Check

int sum(Node* r) {
  if (!r) return 0;
  return sum(r->left) + r->data + sum(r->right);
}

int isSumTree(Node* r) {
  if (!r || (!r->left && !r->right)) return 1;
  if (r->data == sum(r->left) + sum(r->right)
      && isSumTree(r->left)
      && isSumTree(r->right))
    return 1;
  return 0;
}

AVL Balance Factors

After each insert/delete, update BFs up the path. Rotate at deepest unbalanced node.

     Y (bf=2)*
    /    X   T3
  /  T1 T2

LL at Y → right rotate Y:

     X (bf=0)
    /    T1  Y (bf=0)
      /      T2 T3

BuildHeap O(n) — Bottom-Up

Start from last non-leaf (index n/2-1). Sift down each node.

Array: [10, 20, 15, 30, 40, 5, 25, 35]
        10
      /    \
    20      15
   /  \    /  \
 30   40  5   25
/
35

Last non-leaf: idx 3 (val=30)
  → swap 30↔35
  → ... continue sifting up ...
Final heap: [40,35,25,30,20,5,15,10]

Dijkstra Table

Template: V | Known | Dist | Path. Start with source (Dist=0), settle min-dist unvisited each iteration.

Init: A(✓,0,-) B(∞) C(∞) D(∞) E(∞) F(∞)
1. Settle A:    B(4,A) C(2,A)
2. Settle C(2): B(3,C) E(12,C)
3. Settle B(3): D(8,B) E(11,B)
4. Settle D(8): E(10,D) F(14,D)
5. Settle E(10): F(13,E)
6. Settle F(13): done

DP — LCS Matrix

$dp[i][j] =$ LCS of $X[0..i-1]$ and $Y[0..j-1]$

    ""  A  G  G  T  A  B
""  0  0  0  0  0  0  0
G   0  0  1  1  1  1  1
A   0  1  1  1  1  2  2
T   0  1  1  1  2  2  2
A   0  1  1  1  2  3  3
→ LCS = "GATA" (length 4)

0/1 Knapsack DP

$dp[i][w] = \max(dp[i-1][w], \; val[i] + dp[i-1][w - wt[i]])$

Items: (wt,val) = (2,3), (3,4), (4,5), (5,6)
Capacity = 5

    0  1  2  3  4  5
0   0  0  0  0  0  0
(2) 0  0  3  3  3  3
(3) 0  0  3  4  4  7
(4) 0  0  3  4  5  7
(5) 0  0  3  4  5  7
→ Max value = 7 (items 1+2: wt=5, val=7)

Merge Sort Trace

[50, 30, 80, 20, 70, 10, 60, 40]
           /                    \
[50, 30, 80, 20]          [70, 10, 60, 40]
   /         \               /         \
[50,30]    [80,20]       [70,10]    [60,40]
  /  \       /  \         /  \       /  \
[50][30]   [80][20]     [70][10]   [60][40]
  \  /       \  /         \  /       \  /
[30,50]    [20,80]      [10,70]    [40,60]
   \         /            \         /
[20,30,50,80]          [10,40,60,70]
           \            /
    [10,20,30,40,50,60,70,80]