Unit V — Complete Solutions to All Practice Questions

Insert each key — if less than current node go left, if greater go right.

Step-by-step:

1. Insert 45 → root
2. Insert 15 → 15 < 45, go left
3. Insert 79 → 79 > 45, go right
4. Insert 90 → 90 > 45 > 79, go right of 79
5. Insert 10 → 10 < 45 < 15, go left of 15
6. Insert 55 → 55 > 45, right; 55 < 79, left of 79
7. Insert 12 → 12 < 45, left; 12 < 15, left; 12 > 10, right of 10
8. Insert 20 → 20 < 45, left; 20 > 15, right of 15
9. Insert 50 → 50 > 45, right; 50 < 79, left; 50 < 55, left of 55

Final BST:

            45
           /  \
         15    79
        / \   /  \
      10  20 55   90
        \   /
        12 50

Delete 15 (two children):

• In-order successor of 15 is 20 (smallest in right subtree)
• Replace 15 with 20, delete the original 20

            45
           /  \
         20    79
        /     /  \
      10     55   90
        \   /
        12 50

Delete 45 (two children — root):

• In-order successor of 45 is 50 (smallest in right subtree)
• Replace 45 with 50, delete the original 50

            50
           /  \
         20    79
        /     /  \
      10     55   90
        \
        12

Delete 79 (two children):

• In-order successor of 79 is 90 (smallest in right subtree — only child)
• Replace 79 with 90, remove original 90

            50
           /  \
         20    90
        /     /
      10     55
        \
        12

Three cases of BST deletion:

1. Leaf node — simply remove
2. One child — replace with child
3. Two children — replace with in-order successor (or predecessor), then delete successor

Tree from Q1:

            45
           /  \
         15    79
        / \   /  \
      10  20 55   90
        \   /
        12 50

In-order (Left, Root, Right): Visit left subtree, then root, then right subtree.

Note: In-order traversal of a BST always gives sorted order.

Pre-order (Root, Left, Right):

Post-order (Left, Right, Root):

Recursive:

TreeNode* searchRecursive(TreeNode* root, int key) {
    if (root == NULL || root->data == key)
        return root;

    if (key < root->data)
        return searchRecursive(root->left, key);
    else
        return searchRecursive(root->right, key);
}

Iterative:

TreeNode* searchIterative(TreeNode* root, int key) {
    while (root != NULL && root->data != key) {
        if (key < root->data)
            root = root->left;
        else
            root = root->right;
    }
    return root;  // NULL if not found, node if found
}

Inserting sorted array [10, 20, 30, 40, 50]:

Each element is greater than all previous, so it always goes to the right:

10
  \
   20
     \
      30
        \
         40
           \
            50

This creates a skewed tree (essentially a linked list). Height = $n - 1 = 4$. All operations become $O(n)$ instead of $O(\log n)$.

Building a balanced BST from sorted array:

Use the middle element as root recursively:

TreeNode* sortedArrayToBST(int arr[], int left, int right) {
    if (left > right)
        return NULL;

    int mid = (left + right) / 2;
    TreeNode* root = createNode(arr[mid]);
    root->left = sortedArrayToBST(arr, left, mid - 1);
    root->right = sortedArrayToBST(arr, mid + 1, right);
    return root;
}

For [10, 20, 30, 40, 50]:

• Mid = 30 (root)
• Left: [10, 20] → mid = 10 with right child 20
• Right: [40, 50] → mid = 40 with right child 50

       30
      /  \
    10    40
      \     \
      20    50

Height = 2 (balanced!). Operations: $O(\log n)$.

Insert 50: Root = 50

Insert 20: 20 < 50, left child. BFs: 50(+1), 20(0). OK.

Insert 60: 60 > 50, right child. BFs: 50(0), 20(0), 60(0). OK.

    50
   /  \
  20   60

Insert 10: 10 < 50, left; 10 < 20, left. BFs: 50(+2!) → IMBALANCED!

Path: 50 → 20 → 10 (Left-Left) → LL Rotation (Right Rotate at 50)

Before:     After LL rotation:
   50(+2)       20
  /  \          /  \
 20   60      10    50
 /                  /  \
10                (empty) 60

Wait — let me recalculate. BF(20) = 1, BF(50) = 2. LL case.

Right rotate at 50:

       20
      /  \
    10    50
           \
            60

BFs: 20(0), 10(0), 50(-1), 60(0). Balanced!

Insert 8: 8 < 20, left; 8 < 10, left.

       20
      /  \
    10    50
    /      \
   8       60

BFs: 8(0), 10(+1), 20(+1), 50(-1), 60(0). All OK.

Insert 15: 15 < 20, left; 15 > 10, right.

       20
      /  \
    10    50
    / \    \
   8  15   60

BFs: 20(+1), 10(0), 50(-1). OK.

Insert 32: 32 > 20, right; 32 < 50, left.

       20
      /  \
    10    50
    / \  /  \
   8  15 32  60

BFs: 20(0). OK.

Insert 46: 46 > 20, right; 46 < 50, left; 46 > 32, right.

       20
      /  \
    10    50
    / \  /  \
   8  15 32  60
           \
           46

BFs: 32(-1), 50(+1), 20(-1). OK.

Insert 11: 11 < 20, left; 11 > 10, right; 11 < 15, left.

       20
      /  \
    10    50
    / \  /  \
   8  15 32  60
      /    \
     11    46

BFs: 15(+1), 10(-1), 20(+1). OK.

Insert 48: 48 > 20, right; 48 < 50, left; 48 > 32, right; 48 > 46, right.

       20
      /  \
    10    50
    / \  /  \
   8  15 32  60
      /    \
     11    46
             \
             48

BFs: 46(-1), 32(-2!) → IMBALANCED at 32!

Path: 32 → 46 → 48 (Right-Right) → RR Rotation (Left Rotate at 32)

After RR rotation at 32:

       20
      /  \
    10    50
    / \  /  \
   8  15 46  60
      / /  \
     11 32  48

BFs: 46(0), 32(0), 48(0), 50(0). Balanced!

Final AVL Tree:

         20
        /  \
      10    50
      / \  /  \
     8  15 46  60
        / /  \
       11 32  48

Balance Factor (BF) of a node:

An AVL tree is balanced when every node has:

1. LL Rotation (Right Rotation):

Imbalance at node A, caused by insertion into the left subtree of A’s left child.

Before:        After (Right Rotate A):
    A (+2)          B (0)
   /               / \
  B (+1)          C    A (0)
 /
C

2. RR Rotation (Left Rotation):

Imbalance at node A, caused by insertion into the right subtree of A’s right child.

Before:        After (Left Rotate A):
  A (-2)          B (0)
   \             / \
    B (-1)      A    C
     \
      C

3. LR Rotation (Left-Right):

Imbalance at A, caused by insertion into the right subtree of A’s left child. Needs TWO rotations.

Before:           Step 1 (Left Rotate B):    Step 2 (Right Rotate A):
    A (+2)            A (+2)                     C (0)
   /                 /                          / \
  B (-1)            C (+1)                     B    A
   \               /
    C             B

4. RL Rotation (Right-Left):

Imbalance at A, caused by insertion into the left subtree of A’s right child. Needs TWO rotations.

Before:           Step 1 (Right Rotate B):    Step 2 (Left Rotate A):
  A (-2)            A (-2)                      C (0)
   \                 \                          / \
    B (+1)            C (-1)                   A    B
   /                   \
  C                     B

Summary:

The maximum height of an AVL tree with $n$ nodes is:

Practically: $h \approx 1.44 \log_2 n$

This comes from the minimum number of nodes $N(h)$ in an AVL tree of height $h$:

Base cases: $N(0) = 1$, $N(1) = 2$

$N(h)$ grows like Fibonacci numbers: $N(h) \approx \phi^h$ where $\phi = 1.618…$

This means AVL trees guarantee $O(\log n)$ height, making all operations $O(\log n)$.

Why not always use AVL trees?

1. Extra overhead: Each insertion/deletion must check balance and potentially perform rotations
2. More storage: Each node needs to store height or balance factor
3. Insert-heavy workloads: The rotation cost makes AVL slower for frequent insertions
4. Simpler alternatives exist: For random data, a plain BST is often balanced enough
5. Red-black trees offer a middle ground — less strictly balanced but fewer rotations

When to use AVL: When search-heavy workloads demand guaranteed $O(\log n)$ performance (e.g., databases, dictionaries).

Graph:

  A --- B
  |   / |
  |  /  |
  C --- D

Edges: (A,B), (A,C), (B,C), (B,D), (C,D)

Adjacency Matrix (0-indexed: A=0, B=1, C=2, D=3):

Adjacency List:

A → [B, C]
B → [A, C, D]
C → [A, B, D]
D → [B, C]

BFS (Breadth-First Search) — uses Queue:

Queue: [A]        Visit: A
Queue: [B, C]     Visit: B (neighbor of A), C (neighbor of A)
Queue: [C, D]     Visit: C already seen. Visit D (neighbor of B)
Queue: [D]        Visit: D already seen
Queue: []         Done!

BFS Order: A → B → C → D

BFS Trace:

DFS (Depth-First Search) — uses Stack (or recursion):

Start at A → go to first unvisited neighbor B
At B → go to first unvisited neighbor C
At C → go to first unvisited neighbor D
At D → no unvisited neighbors, backtrack

DFS Order: A → B → C → D

(Note: Order depends on the order neighbors are stored. If alphabetical: A→B→C→D)

DFS Trace (recursive):

Topological sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $(u, v)$, vertex $u$ comes before vertex $v$ in the ordering.

Example:

A → B → D
|       ↑
└→ C ───┘

Topological orders: A, B, C, D or A, C, B, D (both valid)

Can it be applied to undirected graphs? NO.

Reasons:

1. No direction — In undirected graphs, edge {A,B} means both A→B and B→A, creating the requirement that A comes before B AND B comes before A — a contradiction.
2. Cycles everywhere — Every edge in an undirected graph forms a cycle of length 2 (A→B→A). Topological sort requires a DAG (no cycles).
3. No partial order — Topological sort relies on a partial order defined by edge direction, which doesn’t exist in undirected graphs.

Algorithm (Kahn’s — BFS-based):

1. Compute in-degree of all vertices
2. Enqueue all vertices with in-degree 0
3. While queue not empty: dequeue $u$, output $u$, reduce in-degree of all neighbors

4. If output count ≠ $

   V

   $, graph has a cycle

Graph (adjacency matrix):

     0   1   2   3   4
0 [  0   4   0   0   8 ]
1 [  4   0   0   2   0 ]
2 [  0   0   0   1   7 ]
3 [  0   2   1   0   0 ]
4 [  8   0   7   0   0 ]

Source: vertex 0

Step 1: From 0: dist[1] = 0+4=4, dist[4] = 0+8=8

Step 2: From 1: dist[3] = min(∞, 4+2) = 6

Step 3: From 3: dist[2] = min(∞, 6+1) = 7, dist[1] = min(4, 6+2) = 4 (no change)

Step 4: From 2: dist[4] = min(8, 7+7) = 8 (no change)

Final shortest distances from 0: {0:0, 1:4, 2:7, 3:6, 4:8}

Shortest paths:

• 0→1: 0→1 (cost 4)
• 0→2: 0→1→3→2 (cost 7)
• 0→3: 0→1→3 (cost 6)
• 0→4: 0→4 (cost 8)

BFS Applications:

• Shortest path in unweighted graphs
• Level-order traversal of trees
• Web crawling (explore nearby pages first)
• Social network — find people within $k$ connections

DFS Applications:

• Topological sorting
• Cycle detection
• Finding connected components
• Solving mazes/puzzles (backtracking)
• Strongly connected components (Tarjan’s, Kosaraju’s)

DAG = Directed Acyclic Graph

A graph that is:

• Directed — edges have direction (arrows)
• Acyclic — no cycles (cannot follow edges in a loop back to the starting vertex)

Real-life example: Course Prerequisites

Math 101 → Math 201 → Math 301
  ↓                      ↑
CS 101 → CS 201 ─────────┘
  ↓
CS 301

Topological sort: Math 101, CS 101, Math 201, CS 201, CS 301, Math 301

This ordering ensures you take prerequisites before any course that depends on them.

Other examples:

• Build systems: Compile dependencies in order (Makefiles)
• Task scheduling: Complete prerequisite tasks first
• Package managers: Install dependencies before the package
• Spreadsheet formulas: Evaluate cells that others depend on first

Method: Build using bottom-up heapify. Start from the last non-leaf node (index $\lfloor n/2 \rfloor - 1 = 2$).

Initial array as tree:

        4
       / \
     10    3
    / \   / \
   5   1 8   7

Heapify index 2 (value 3): Children: 8, 7. Max child = 8 > 3 → swap.

        4
       / \
     10    8
    / \   / \
   5   1 3   7

Heapify index 1 (value 10): Children: 5, 1. Max child = 5 < 10 → no swap.

Heapify index 0 (value 4): Children: 10, 8. Max child = 10 > 4 → swap.

       10
       / \
      4    8
    / \   / \
   5   1 3   7

Now heapify down index 1 (value 4): Children: 5, 1. Max child = 5 > 4 → swap.

       10
       / \
      5    8
    / \   / \
   4   1 3   7

Final max-heap: [10, 5, 8, 4, 1, 3, 7]

Verification: Every parent ≥ its children. ✓

Heap: [10, 5, 8, 4, 1, 3, 7]

Extract 1 — Remove 10: Swap root (10) with last element (7), remove 10, heapify down.

[7, 5, 8, 4, 1, 3]
→ 7 < 8 → swap with 8
[8, 5, 7, 4, 1, 3]
→ 7 > 3 → no more swaps

Extracted: 10. Heap: [8, 5, 7, 4, 1, 3]

Extract 2 — Remove 8: Swap root (8) with last element (3), remove 8, heapify down.

[3, 5, 7, 4, 1]
→ 3 < 7 → swap with 7
[7, 5, 3, 4, 1]
→ 3 has no children below → done

Extracted: 8. Heap: [7, 5, 3, 4, 1]

Extract 3 — Remove 7: Swap root (7) with last element (1), remove 7, heapify down.

[1, 5, 3, 4]
→ 1 < 5 → swap with 5
[5, 1, 3, 4]
→ 1 < 4 → swap with 4
[5, 4, 3, 1]

Extracted: 7. Heap: [5, 4, 3, 1]

Elements extracted in order: 10, 8, 7 (decreasing — this is Heap Sort!)

Max-Heap example:

       50
      /  \
    30    40
   / \
  10  20

Root = 50 (maximum)

Min-Heap example:

       10
      /  \
    20    30
   / \
  50  40

Root = 10 (minimum)

A binary heap is a complete binary tree — all levels are fully filled except possibly the last, which is filled left to right. This property makes array storage ideal:

Array index formulas (0-indexed):

• Parent of node $i$: $\lfloor (i-1)/2 \rfloor$
• Left child of node $i$: $2i + 1$
• Right child of node $i$: $2i + 2$

Advantages of array storage:

Why it works: The complete tree property guarantees no “gaps” in the array. Every index from 0 to $n-1$ is used.

This would NOT work for BSTs or AVL trees because they are not necessarily complete.

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    // Step 1: Build max-heap (O(n))
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Step 2: Extract elements one by one (O(n log n))
    for (int i = n - 1; i > 0; i--) {
        // Swap root (max) with last element
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // Heapify reduced heap
        heapify(arr, i, 0);
    }
}

Trace for [4, 10, 3, 5, 1]:

Build heap: [10, 5, 3, 4, 1]

Sorted: [1, 3, 4, 5, 10]

Hashing is a technique that maps data (keys) to fixed-size values (hash codes) using a hash function, which determines the index/slot in a hash table where the data is stored.

Why hashing is useful:

Applications:

• Dictionaries / Symbol tables (compilers)
• Database indexing
• Caching (memoization)
• Password storage (hash + salt)
• Data deduplication
• Sets (checking membership in $O(1)$)

Hash function: $h(k) = k \mod 7$

(a) Separate Chaining:

Each slot is a linked list:

(b) Linear Probing ($h(k, i) = (h(k) + i) \mod 7$):

Table: [42, 57, 67, 101, 25, 96, 31]

(c) Quadratic Probing ($h(k, i) = (h(k) + i^2) \mod 7$):

With table size 7 (prime), quadratic probing can fail when table is > half full. Some keys may need rehashing.

31 goes to index 2 (trying alternate sequence) or requires table resize.

67: $h = 4$, $i=1: 5$ full, $i=2: (4+4)\%7=1$ full, $i=3: (4+9)\%7=6$→6.

Collision: When two or more keys hash to the same index: $h(k_1) = h(k_2)$ but $k_1 \neq k_2$.

All are open addressing methods — when a collision occurs, probe for the next empty slot.

1. Linear Probing: $h(k, i) = (h(k) + i) \mod m$

Probe sequence: $h(k), h(k)+1, h(k)+2, \ldots$

Problem: Primary clustering — long clusters of occupied slots form, slowing searches.

2. Quadratic Probing: $h(k, i) = (h(k) + i^2) \mod m$

Probe sequence: $h(k), h(k)+1, h(k)+4, h(k)+9, \ldots$

Better than linear — jumps further, reduces primary clustering. Problem: Secondary clustering — keys with the same hash follow the same probe sequence.

3. Double Hashing: $h(k, i) = (h_1(k) + i \cdot h_2(k)) \mod m$

Uses a second hash function to determine the step size. Common choice: $h_2(k) = R - (k \mod R)$ where $R$ is a prime < $m$.

Example with m=7, keys: 10, 17, 24

$h(k) = k \mod 7$. All three hash to index 3!

Double hashing gives the most uniform distribution of probes.

Where $n$ = number of keys stored, $m$ = table size.

Effect on performance (Open Addressing with Uniform Hashing):

Formulas:

• Unsuccessful search: $\frac{1}{1-\alpha}$
• Successful search: $\frac{1}{\alpha} \ln \frac{1}{1-\alpha}$

For Separate Chaining:

• Average chain length = $\alpha$ (can exceed 1)
• Unsuccessful search: $O(1 + \alpha)$
• Successful search: $O(1 + \alpha/2)$

Best practice: Keep $\alpha < 0.75$ for open addressing. Rehash (double table size) when threshold is exceeded.

Reason: A prime table size reduces the chance of patterns in key values causing clustering.

Example — Non-prime size (m=10): If keys are multiples of 5: 5, 10, 15, 20, 25…

• $5 \mod 10 = 5$
• $10 \mod 10 = 0$
• $15 \mod 10 = 5$ → collision!
• $20 \mod 10 = 0$ → collision!

Only slots 0 and 5 are used — terrible distribution.

Example — Prime size (m=7): Same keys: 5, 10, 15, 20, 25

• $5 \mod 7 = 5$
• $10 \mod 7 = 3$
• $15 \mod 7 = 1$
• $20 \mod 7 = 6$
• $25 \mod 7 = 4$

All different slots — much better distribution!

Mathematical reason: When $m$ is prime, it shares no common factors with the key (unless the key is a multiple of $m$). This means the modulo operation distributes keys more uniformly. With composite $m$, keys that share a factor with $m$ tend to cluster.

Additional reasons:

• Quadratic probing is guaranteed to visit all slots only when $m$ is prime
• Double hashing works best with prime table sizes

Examples:

Complete:       Full:          Neither:
    1             1               1
   / \           / \             / \
  2   3         2   3           2   3
 / \           / \               \
4   5         4   5               5

Sample tree:
      1
     / \
    2   3
   / \
  4   5

Mnemonics:

• In-order: Root is in the middle
• Pre-order: Root comes first (pre = before)
• Post-order: Root comes last (post = after)

In-order visits: left subtree → root → right subtree.

By the BST property:

• All nodes in the left subtree have values less than the root
• All nodes in the right subtree have values greater than the root

So in-order traversal visits all smaller values first (left subtree), then the current value (root), then all larger values (right subtree). Recursively, this produces values in ascending order.

Proof by induction: If in-order traversal of any BST subtree gives sorted output, then visiting left (sorted, all < root) + root + right (sorted, all > root) = sorted sequence for the whole subtree.

$BF = Height(Left) - Height(Right)$

A tree is a special case of a graph: a connected, acyclic, undirected graph.

Hashing maps keys to table indices using a hash function for $O(1)$ average-case access.

Three hash functions:

1. Division Method: $h(k) = k \mod m$ — simple, effective when $m$ is prime.

2. Mid-Square Method: Square the key, extract middle digits. $h(k) = \text{middle digits of } k^2$.

3. Multiplication Method: $h(k) = \lfloor m \cdot (kA \mod 1) \rfloor$ where $A \approx 0.6180339887$ (Knuth’s suggestion).

         50
        /  \
      30    70
     / \   /  \
   20  40 60   80

In-order: 20, 30, 40, 50, 60, 70, 80 (sorted!)

Pre-order: 50, 30, 20, 40, 70, 60, 80

Post-order: 20, 40, 30, 60, 80, 70, 50

Insert 30, 20: No imbalance.

    30
   /
  20

Insert 10: BF(30) = +2 → LL Rotation (right rotate at 30)

Before:       After:
  30(+2)       20
 /            /  \
20(+1)      10    30
/
10

Insert 25: 25 > 20, right; 25 < 30, left.

    20
   /  \
  10   30
      /
     25

BFs: 30(+1), 20(-1). OK.

Insert 40: 40 > 20, right; 40 > 30, right.

    20
   /  \
  10   30
      /  \
     25   40

BFs: 30(0), 20(-1). OK.

Insert 35: 35 > 20, right; 35 > 30, right; 35 < 40, left.

    20
   /  \
  10   30
      /  \
     25   40
         /
        35

BFs: 40(+1), 30(-2!) → RL Rotation at 30.

Step 1 — Right rotate at 40:

    20
   /  \
  10   30
      /  \
     25   35
            \
            40

Step 2 — Left rotate at 30:

    20
   /  \
  10   35
      /  \
     30   40
    /
   25

BFs: 30(+1), 35(+1), 20(-1). All OK!

Final AVL tree:

       20
      /  \
    10    35
         /  \
        30   40
       /
      25

Graph:

  A --- B --- E
  |         / |
  C --- D     F

Edges: (A,B), (A,C), (B,E), (C,D), (D,E), (E,F)

BFS (from A, using Queue):

BFS Order: A, B, C, E, D, F

DFS (from A, recursive):

dfs(A) → visit A, neighbors: B, C
  dfs(B) → visit B, neighbors: A✓, E
    dfs(E) → visit E, neighbors: B✓, D, F
      dfs(D) → visit D, neighbors: C, E✓
        dfs(C) → visit C, neighbors: A✓, D✓ → backtrack
      backtrack from D
      dfs(F) → visit F, neighbors: E✓ → backtrack
    backtrack from E
  backtrack from B
backtrack from A

DFS Order: A, B, E, D, C, F

Graph:

  S --2-- A --3-- D
  |       |       |
  6       1       5
  |       |       |
  B --4-- C --2-- E

Trace details:

• From S: dist[A] = 2, dist[B] = 6
• From A: dist[C] = min(∞, 2+1) = 3, dist[D] = min(∞, 2+3) = 5
• From C: dist[B] = min(6, 3+4) = 6 (no change), dist[E] = min(∞, 3+2) = 5
• From D: dist[E] = min(5, 5+5) = 5 (no change)
• From E: no improvements

Shortest distances from S: S=0, A=2, B=6, C=3, D=5, E=5

Shortest paths:

• S→A: S→A (2)
• S→B: S→B (6)
• S→C: S→A→C (3)
• S→D: S→A→D (5)
• S→E: S→A→C→E (5)

Build max-heap (bottom-up heapify):

Initial tree:

      3
     / \
    1   6
   / \ /
  5  2 4

Heapify index 2 (value 6): children: 4. 6 > 4 → OK.

Heapify index 1 (value 1): children: 5, 2. Max = 5 > 1 → swap.

      3
     / \
    5   6
   / \ /
  1  2 4

Heapify index 0 (value 3): children: 5, 6. Max = 6 > 3 → swap.

      6
     / \
    5   3
   / \ /
  1  2 4

Continue heapifying 3: child 4 > 3 → swap.

      6
     / \
    5   4
   / \ /
  1  2 3

Max-heap: [6, 5, 4, 1, 2, 3]

Extract max 1 — Remove 6: Swap 6 with last (3): [3, 5, 4, 1, 2]. Pop 6. Heapify: 3 < 5 → swap. [5, 3, 4, 1, 2]. 3 > 1 and 2 → OK.

Heap: [5, 3, 4, 1, 2]. Extracted: 6.

Extract max 2 — Remove 5: Swap 5 with last (2): [2, 3, 4, 1]. Pop 5. Heapify: 2 < 4 → swap. [4, 3, 2, 1]. OK.

Heap: [4, 3, 2, 1]. Extracted: 5.

Hash function: $h(k) = k \mod 11$

(a) Separate Chaining:

(b) Linear Probing:

Final table:

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void preorder(TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void postorder(TreeNode* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

Trace on tree:

      1
     / \
    2   3
   / \
  4   5

In-order trace:

inorder(1) → inorder(2) → inorder(4) → inorder(NULL) → return
                                       → print 4
                                       → inorder(NULL) → return
                          → print 2
                          → inorder(5) → inorder(NULL) → print 5 → inorder(NULL)
             → print 1
             → inorder(3) → inorder(NULL) → print 3 → inorder(NULL)

Output: 4 2 5 1 3

Time: $O(n)$, Space: $O(h)$ where $h$ is the tree height.

Insertion: Compare key with root, go left if smaller, right if larger, insert when NULL is reached.

TreeNode* insert(TreeNode* root, int key) {
    if (root == NULL) return createNode(key);
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    return root;
}

Deletion — Three cases:

Case 1: Leaf node — Simply remove it.

Delete 4:
    5          5
   / \   →    / \
  3   7      3   7
 /
4

Case 2: One child — Replace node with its child.

Delete 3 (has left child 2):
    5          5
   / \   →   / \
  3   7     2   7
 /
2

Case 3: Two children — Replace with in-order successor (smallest in right subtree) or predecessor.

Delete 5 (root, has two children):
  In-order successor of 5 = 7
    5          7
   / \   →   /
  3   7     3

TreeNode* deleteNode(TreeNode* root, int key) {
    if (root == NULL) return NULL;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // Node found
        if (root->left == NULL) {       // Case 1 & 2
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) { // Case 2
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // Case 3: Two children
        TreeNode* succ = root->right;
        while (succ->left != NULL) succ = succ->left;
        root->data = succ->data;
        root->right = deleteNode(root->right, succ->data);
    }
    return root;
}

See Q3 of AVL Tree section for detailed rotation diagrams.

Why AVL over BST:

• BST can degrade to $O(n)$ for sorted/nearly-sorted input (skewed tree)
• AVL guarantees $O(\log n)$ for ALL operations
• Critical for databases and real-time systems where worst-case performance matters

Trade-off: AVL has rotation overhead per insert/delete — worth it only when search frequency significantly exceeds modification frequency.

See Q5 of Graphs section for the detailed comparison table.

Key difference in behavior:

Graph:  A - B - E
        |       |
        C - D - F

BFS from A: A, B, C, E, D, F  (level by level)
DFS from A: A, B, E, D, C, F  (deep first, then backtrack)

BFS explores all neighbors before going deeper. DFS goes as deep as possible before backtracking.

See Q4 of Graphs section for a complete trace, or Q10 of Comprehensive section for another example.

Algorithm summary:

1. Initialize: dist[source] = 0, all others = ∞
2. Repeat V times: Pick unvisited vertex $u$ with minimum dist
3. For each neighbor $v$ of $u$: if $dist[u] + weight(u,v) < dist[v]$, update $dist[v]$
4. Mark $u$ as visited

Time: $O(V^2)$ with array, $O((V+E)\log V)$ with min-heap

Limitation: Does NOT work with negative edge weights (use Bellman-Ford instead).

See Q3 and Q4 of the Hashing section for detailed explanations.

Summary comparison:

Priority Queue: An ADT where elements have priorities. The highest-priority element is served first regardless of insertion order.

Binary Heap is the most common implementation:

Insert (Heap Up / Sift Up):

void insert(int heap[], int* n, int value) {
    heap[*n] = value;
    int i = *n;
    (*n)++;
    while (i > 0 && heap[i] > heap[(i-1)/2]) {
        int temp = heap[i];
        heap[i] = heap[(i-1)/2];
        heap[(i-1)/2] = temp;
        i = (i - 1) / 2;
    }
}

Extract Max (Heap Down / Sift Down):

int extractMax(int heap[], int* n) {
    int max = heap[0];
    (*n)--;
    heap[0] = heap[*n];
    heapify(heap, *n, 0);
    return max;
}

Example: Insert 15 into max-heap [20, 10, 8, 5, 3]:

[20, 10, 8, 5, 3, 15]
15 > parent(8) → swap: [20, 10, 15, 5, 3, 8]
15 > parent(20)? No → done.

Topological sorting produces a linear ordering of vertices in a DAG such that for every directed edge $u \to v$, $u$ appears before $v$.

Applicable only to DAGs (Directed Acyclic Graphs). Cannot be applied to:

• Undirected graphs
• Graphs with cycles

Kahn’s Algorithm (BFS-based):

1. Compute in-degree of all vertices
2. Enqueue all vertices with in-degree 0
3. While queue not empty:
   a. Dequeue vertex u, add to result
   b. For each neighbor v of u:
      - Decrease in-degree[v] by 1
      - If in-degree[v] == 0, enqueue v
4. If result size ≠ |V|, graph has a cycle

Trace on DAG:

  A → B → D
  ↓       ↑
  C ──────┘

Edges: A→B, A→C, B→D, C→D

In-degrees: A=0, B=1, C=1, D=2

Topological Order: A, B, C, D ✓

Also valid: A, C, B, D (multiple valid orderings exist).

DFS-based approach: Run DFS and push each vertex to a stack after all its descendants are processed. Pop the stack for topological order.

Time: $O(V + E)$ for both algorithms.