1. Types of Data Structures

Primitive Data Structures:

• Integer, Float, Character, Boolean

• Directly operated by machine instructions

Non-Primitive Data Structures:

• Linear: Array, Stack, Queue, Linked List

• Non-Linear: Tree, Graph

---

2. Linear vs Non-Linear Data Structures

Linear Data Structures:

• Elements arranged in sequential order

• Each element has a predecessor and successor (except first and last)

• Examples: Array, Stack, Queue, Linked List

• Traversal: Single run through all elements

• Memory: May be sequential or non-sequential

Non-Linear Data Structures:

• Elements not arranged sequentially

• Hierarchical or network relationships

• Examples: Tree, Graph

• Traversal: Multiple paths possible

• Memory: Non-sequential

---

3. Operations in DSA

Basic Operations:

• Insertion: Adding new element

• Deletion: Removing an element

• Searching: Finding an element

• Traversal: Visiting all elements

• Sorting: Arranging in order

• Merging: Combining two structures

---

4. Structure vs Union & Self-Referential Structure

Structure vs Union:

struct Student {
    int roll;
    char name[50];
}; // Size = 4 + 50 = 54 bytes

union Data {
    int i;
    float f;
    char c;
}; // Size = 4 bytes (largest)

Self-Referential Structure: Structure containing pointer to same structure type.

struct Node {
    int data;
    struct Node *next; // Points to same type
};

---

5. Nested Structure

Structure inside another structure.

struct Address {
    char city[30];
    int pin;
};

struct Employee {
    int id;
    char name[50];
    struct Address addr; // Nested structure
};

int main() {
    struct Employee e;
    e.id = 101;
    strcpy(e.addr.city, "Kolkata");
}

---

6. Structure to Store Student Info

struct Student {
    int roll_no;
    char name[50];
    float marks[5];
    float total;
    float percentage;
};

int main() {
    struct Student s;
    printf("Enter Roll No: ");
    scanf("%d", &s.roll_no);
    printf("Enter Name: ");
    scanf("%s", s.name);

    s.total = 0;
    for(int i = 0; i < 5; i++) {
        printf("Enter marks for subject %d: ", i+1);
        scanf("%f", &s.marks[i]);
        s.total += s.marks[i];
    }
    s.percentage = s.total / 5;

    printf("\nRoll: %d\nName: %s\nPercentage: %.2f", 
           s.roll_no, s.name, s.percentage);
}

---

7. Differences - Set A

A) Stack vs Queue

B) AVL Tree vs BST

C) Linear vs Binary Search

D) Array vs Linked List

E) Hashing vs Searching

---

8. Differences - Set B

A) Linear vs Circular Queue

B) Recursion vs Iteration

C) Internal vs External Sorting

---

9. Binary Search Implementation & Time Complexity

int binarySearch(int arr[], int n, int key) {
    int low = 0, high = n - 1;

    while(low <= high) {
        int mid = (low + high) / 2;

        if(arr[mid] == key)
            return mid; // Found
        else if(arr[mid] < key)
            low = mid + 1; // Search right half
        else
            high = mid - 1; // Search left half
    }
    return -1; // Not found
}

Time Complexity Calculation:

• Each iteration divides search space by 2

• After k iterations: n/2^k elements remain

• When 1 element left: n/2^k = 1

• Therefore: 2^k = n

• k = log₂(n)

Time Complexity: O(log n) Space Complexity: O(1)

---

10. Push, Pop Algorithms & Infix to Postfix

Push Algorithm (Stack)

void push(int stack[], int *top, int max, int value) {
    if(*top == max - 1) {
        printf("Stack Overflow\n");
        return;
    }
    (*top)++;
    stack[*top] = value;
}

Pop Algorithm (Stack)

int pop(int stack[], int *top) {
    if(*top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    int value = stack[*top];
    (*top)--;
    return value;
}

Infix to Postfix Conversion

Example: A + B * C - D / E

Algorithm:

1. Scan expression left to right

2. If operand, add to output

3. If operator, pop operators with higher/equal precedence, then push

4. If '(', push to stack

5. If ')', pop until '('

6. At end, pop all operators

Step-by-step:

Input: A + B * C - D / E

Symbol  Stack   Output
A       -       A
+       +       A
B       +       AB
*       +*      AB
C       +*      ABC
-       -       ABC*+
D       -       ABC*+D
/       -/      ABC*+D
E       -/      ABC*+DE
End     -       ABC*+DE/-

Result: ABC*+DE/-

Operator Precedence:

• ^ : 3

• *, / : 2

• +, - : 1

---

11. Stack Implementation

Using Array

#define MAX 100

typedef struct {
    int arr[MAX];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == MAX - 1;
}

void push(Stack *s, int value) {
    if(isFull(s)) {
        printf("Stack Overflow\n");
        return;
    }
    s->arr[++s->top] = value;
}

int pop(Stack *s) {
    if(isEmpty(s)) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->arr[s->top--];
}

int peek(Stack *s) {
    if(isEmpty(s))
        return -1;
    return s->arr[s->top];
}

Using Linked List

typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *top = NULL;

void push(int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = top;
    top = newNode;
}

int pop() {
    if(top == NULL) {
        printf("Stack Underflow\n");
        return -1;
    }
    Node *temp = top;
    int value = temp->data;
    top = top->next;
    free(temp);
    return value;
}

int isEmpty() {
    return top == NULL;
}

---

12. Row Major vs Column Major Order

For 2D Array A[m][n]:

Row Major Order

Elements stored row by row.

Address Formula:

Address(A[i][j]) = Base + [(i × n) + j] × size

Example: A[3][4]

Storage: A[0][0], A[0][1], A[0][2], A[0][3], 
         A[1][0], A[1][1], A[1][2], A[1][3],
         A[2][0], A[2][1], A[2][2], A[2][3]

Column Major Order

Elements stored column by column.

Address Formula:

Address(A[i][j]) = Base + [(j × m) + i] × size

Example: A[3][4]

Storage: A[0][0], A[1][0], A[2][0], 
         A[0][1], A[1][1], A[2][1],
         A[0][2], A[1][2], A[2][2],
         A[0][3], A[1][3], A[2][3]

---

13. Circular Queue Operations

Insertion (Enqueue)

void enqueue(int queue[], int *front, int *rear, int max, int value) {
    if((*rear + 1) % max == *front) {
        printf("Queue Full\n");
        return;
    }
    if(*front == -1)
        *front = 0;
    *rear = (*rear + 1) % max;
    queue[*rear] = value;
}

Deletion (Dequeue)

int dequeue(int queue[], int *front, int *rear, int max) {
    if(*front == -1) {
        printf("Queue Empty\n");
        return -1;
    }
    int value = queue[*front];
    if(*front == *rear) { // Only one element
        *front = *rear = -1;
    } else {
        *front = (*front + 1) % max;
    }
    return value;
}

---

14. Linear Queue Implementation

Using Array

#define MAX 100

typedef struct {
    int arr[MAX];
    int front, rear;
} Queue;

void initialize(Queue *q) {
    q->front = q->rear = -1;
}

void enqueue(Queue *q, int value) {
    if(q->rear == MAX - 1) {
        printf("Queue Full\n");
        return;
    }
    if(q->front == -1)
        q->front = 0;
    q->arr[++q->rear] = value;
}

int dequeue(Queue *q) {
    if(q->front == -1 || q->front > q->rear) {
        printf("Queue Empty\n");
        return -1;
    }
    return q->arr[q->front++];
}

Using Linked List

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front, *rear;
} Queue;

void enqueue(Queue *q, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if(q->rear == NULL) {
        q->front = q->rear = newNode;
        return;
    }
    q->rear->next = newNode;
    q->rear = newNode;
}

int dequeue(Queue *q) {
    if(q->front == NULL) {
        printf("Queue Empty\n");
        return -1;
    }
    Node *temp = q->front;
    int value = temp->data;
    q->front = q->front->next;

    if(q->front == NULL)
        q->rear = NULL;

    free(temp);
    return value;
}

---

15. Priority Queue & Deque

Priority Queue

Queue where elements are served based on priority, not FIFO order.

typedef struct {
    int data;
    int priority;
} Element;

typedef struct {
    Element arr[MAX];
    int size;
} PriorityQueue;

void enqueue(PriorityQueue *pq, int data, int priority) {
    if(pq->size == MAX) return;

    int i = pq->size - 1;
    while(i >= 0 && pq->arr[i].priority > priority) {
        pq->arr[i + 1] = pq->arr[i];
        i--;
    }
    pq->arr[i + 1].data = data;
    pq->arr[i + 1].priority = priority;
    pq->size++;
}

int dequeue(PriorityQueue *pq) {
    if(pq->size == 0) return -1;
    return pq->arr[--pq->size].data;
}

Deque (Double-Ended Queue)

Insertion and deletion at both ends.

Types:

• Input Restricted: Insertion at one end only, deletion at both ends

• Output Restricted: Insertion at both ends, deletion at one end only

void insertFront(int deque[], int *front, int *rear, int max, int value);
void insertRear(int deque[], int *front, int *rear, int max, int value);
int deleteFront(int deque[], int *front, int *rear);
int deleteRear(int deque[], int *front, int *rear);

---

16. Doubly Linked List Better Than Singly

Advantages of Doubly Linked List:

1. Bidirectional Traversal: Can move forward and backward

2. Easier Deletion: Can delete node with only pointer to it

3. Reverse Traversal: Can traverse in reverse efficiently

4. Insert Before Node: Easy to insert before a given node

Disadvantages:

• More memory (extra pointer)

• More complex operations

struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
};

---

17. Bubble Sort Implementation

void bubbleSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int swapped = 0;
        for(int j = 0; j < n - i - 1; j++) {
            if(arr[j] > arr[j + 1]) {
                // Swap
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = 1;
            }
        }
        // If no swap, array is sorted
        if(swapped == 0)
            break;
    }
}

// Example usage
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = 7;

    bubbleSort(arr, n);

    printf("Sorted array: ");
    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Time Complexity:

• Best Case: O(n) - when already sorted

• Average Case: O(n²)

• Worst Case: O(n²)

Space Complexity: O(1)

---

18. Polynomial Representation Using Linked List

typedef struct Node {
    int coeff;   // Coefficient
    int exp;     // Exponent
    struct Node *next;
} Node;

Node* createNode(int coeff, int exp) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->coeff = coeff;
    newNode->exp = exp;
    newNode->next = NULL;
    return newNode;
}

void insertTerm(Node **poly, int coeff, int exp) {
    Node *newNode = createNode(coeff, exp);

    if(*poly == NULL) {
        *poly = newNode;
        return;
    }

    Node *temp = *poly;
    while(temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

void display(Node *poly) {
    while(poly != NULL) {
        printf("%dx^%d", poly->coeff, poly->exp);
        poly = poly->next;
        if(poly != NULL)
            printf(" + ");
    }
    printf("\n");
}

Example: 5x³ + 4x² + 2x⁰

[5,3] -> [4,2] -> [2,0] -> NULL

---

19. Polynomial Addition Using Linked List

Node* addPolynomials(Node *poly1, Node *poly2) {
    Node *result = NULL;
    Node *tail = NULL;

    while(poly1 != NULL && poly2 != NULL) {
        Node *newNode = NULL;

        if(poly1->exp > poly2->exp) {
            newNode = createNode(poly1->coeff, poly1->exp);
            poly1 = poly1->next;
        }
        else if(poly1->exp < poly2->exp) {
            newNode = createNode(poly2->coeff, poly2->exp);
            poly2 = poly2->next;
        }
        else { // Equal exponents
            int sum = poly1->coeff + poly2->coeff;
            if(sum != 0) {
                newNode = createNode(sum, poly1->exp);
            }
            poly1 = poly1->next;
            poly2 = poly2->next;
        }

        if(newNode != NULL) {
            if(result == NULL) {
                result = tail = newNode;
            } else {
                tail->next = newNode;
                tail = newNode;
            }
        }
    }

    // Add remaining terms
    while(poly1 != NULL) {
        tail->next = createNode(poly1->coeff, poly1->exp);
        tail = tail->next;
        poly1 = poly1->next;
    }

    while(poly2 != NULL) {
        tail->next = createNode(poly2->coeff, poly2->exp);
        tail = tail->next;
        poly2 = poly2->next;
    }

    return result;
}

---

20. All Linked List Algorithms

Singly Linked List

Insertion at Beginning:

void insertAtBeginning(Node **head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = *head;
    *head = newNode;
}

Insertion at End:

void insertAtEnd(Node **head, int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;

    if(*head == NULL) {
        *head = newNode;
        return;
    }

    Node *temp = *head;
    while(temp->next != NULL)
        temp = temp->next;
    temp->next = newNode;
}

Deletion:

void deleteNode(Node **head, int key) {
    Node *temp = *head, *prev = NULL;

    if(temp != NULL && temp->data == key) {
        *head = temp->next;
        free(temp);
        return;
    }

    while(temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if(temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

Search:

int search(Node *head, int key) {
    while(head != NULL) {
        if(head->data == key)
            return 1;
        head = head->next;
    }
    return 0;
}

Reverse:

void reverse(Node **head) {
    Node *prev = NULL, *current = *head, *next = NULL;

    while(current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head = prev;
}

Display:

void display(Node *head) {
    while(head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

---

21. Largest and Smallest Number Algorithm

void findLargestSmallest(int arr[], int n) {
    if(n == 0) {
        printf("Array is empty\n");
        return;
    }

    int largest = arr[0];
    int smallest = arr[0];

    for(int i = 1; i < n; i++) {
        if(arr[i] > largest)
            largest = arr[i];
        if(arr[i] < smallest)
            smallest = arr[i];
    }

    printf("Largest: %d\n", largest);
    printf("Smallest: %d\n", smallest);
}

Time Complexity: O(n) Space Complexity: O(1)

---

22. Static vs Dynamic Memory Allocation

Static Example:

int arr[100]; // Size fixed at compile time

Dynamic Example:

int *arr = (int*)malloc(n * sizeof(int)); // Size decided at runtime
free(arr); // Must free manually

---

23. malloc() vs calloc()

malloc Example:

int *arr = (int*)malloc(5 * sizeof(int));
// Contains garbage values
free(arr);

calloc Example:

int *arr = (int*)calloc(5, sizeof(int));
// All elements initialized to 0
free(arr);

realloc():

int *arr = (int*)malloc(5 * sizeof(int));
arr = (int*)realloc(arr, 10 * sizeof(int)); // Resize to 10 elements

---

24. AVL Tree & Rotations

AVL Tree: Self-balancing BST where height difference between left and right subtrees ≤ 1.

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

Values: -1, 0, or 1 (balanced)

Types of Rotations:

1. Left-Left (LL) Rotation:

    z                      y
   /                      / \
  y        -->           x   z
 /
x

2. Right-Right (RR) Rotation:

x                          y
 \                        / \
  y        -->           x   z
   \
    z

3. Left-Right (LR) Rotation:

  z                z                  y
 /                /                  / \
y        -->     y        -->       x   z
 \              /
  x            x

4. Right-Left (RL) Rotation:

x              x                    y
 \              \                  / \
  z      -->     y       -->      x   z
 /                \
y                  z

C Implementation (LL Rotation):

struct Node* rightRotate(struct Node *y) {
    struct Node *x = y->left;
    struct Node *T2 = x->right;

    x->right = y;
    y->left = T2;

    // Update heights
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

---

25. AVL Tree Construction: 8,12,9,11,7,6,66,2,1,44

Step-by-step insertion:

Insert 8:

8

Insert 12:

  8
   \
   12

Insert 9: (RR case on 8-12-9)

  8              9
   \            / \
   12    -->   8  12
  /
 9

Insert 11:

    9
   / \
  8  12
     /
    11

Insert 7:

    9
   / \
  8  12
 /   /
7   11

Insert 6: (LL case on 8-7-6)

      9
     / \
    7  12
   / \  /
  6  8 11

Insert 66:

      9
     / \
    7  12
   / \  / \
  6  8 11 66

Insert 2:

      9
     / \
    7  12
   / \  / \
  6  8 11 66
 /
2

Insert 1: (Rebalancing needed)

      9
     / \
    6  12
   / \  / \
  2  7 11 66
 / \
1  8

Insert 44:

        9
      /   \
     6     12
    / \    / \
   2   7  11 66
  / \        /
 1   8      44

Final AVL Tree is balanced with all balance factors in {-1, 0, 1}

---

26. Tree Traversal & Construction

Preorder, Inorder, Postorder

Given Tree:

       A
      / \
     B   C
    / \   \
   D   E   F

• Preorder (Root-Left-Right): A B D E C F

• Inorder (Left-Root-Right): D B E A C F

• Postorder (Left-Right-Root): D E B F C A

Construct Tree from Traversals

Given:

• Postorder: I E J F C G L H D B A

• Inorder: E I C F J B G D K H L A

Solution:

1. Last element in postorder is root: A

2. Find A in inorder: Elements before A are left subtree, after are right

   • Left: E I C F J B G D K H L

   • Right: (none)

3. In postorder, before A: I E J F C G L H D B

   • Elements belonging to left subtree: I E J F C G L H D B

4. Continue recursively...

Constructed Tree:

                A
               /
              B
             / \
            C   D
           / \   / \
          I   F G   H
         /   /     / \
        E   J     K   L

---

27. Quick Sort with Time Complexity

Algorithm:

1. Choose pivot element (usually last element)

2. Partition: elements < pivot on left, > pivot on right

3. Recursively sort left and right partitions

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for(int j = low; j < high; j++) {
        if(arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Swap arr[i+1] and arr[high]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if(low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Left partition
        quickSort(arr, pi + 1, high); // Right partition
    }
}

// Usage
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = 6;
    quickSort(arr, 0, n - 1);

    for(int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

Time Complexity:

• Best Case: O(n log n) - balanced partitions

• Average Case: O(n log n)

• Worst Case: O(n²) - already sorted array

Space Complexity: O(log n) - recursion stack

---

28. Algorithm Performance & Rehashing (Continued)

Algorithm Performance Metrics

1. Time Complexity: Amount of time taken 2. Space Complexity: Amount of memory used 3. Best Case: Minimum time needed 4. Average Case: Expected time for random input 5. Worst Case: Maximum time needed

Asymptotic Notations:

• Big O (O): Upper bound - worst case

• Omega (Ω): Lower bound - best case

• Theta (Θ): Tight bound - average case

Common Time Complexities (from fastest to slowest):

• O(1) - Constant

• O(log n) - Logarithmic

• O(n) - Linear

• O(n log n) - Linearithmic

• O(n²) - Quadratic

• O(n³) - Cubic

• O(2ⁿ) - Exponential

Rehashing

Problem: When hash table becomes too full (high load factor), collisions increase and performance degrades.

Solution: Rehashing - create a larger hash table and rehash all elements.

When to Rehash:

• When load factor (n/table_size) exceeds threshold (usually 0.7 or 0.75)

• After too many collisions

Rehashing Process:

void rehash(HashTable *ht) {
    int oldSize = ht->size;
    Element *oldTable = ht->table;

    // Create new table with double size
    ht->size = oldSize * 2;
    ht->table = (Element*)calloc(ht->size, sizeof(Element));
    ht->count = 0;

    // Rehash all elements
    for(int i = 0; i < oldSize; i++) {
        if(oldTable[i].key != -1) {
            insert(ht, oldTable[i].key, oldTable[i].value);
        }
    }

    free(oldTable);
}

Load Factor = Number of elements / Table size

---

29. Merge Sort, Sparse Matrix

Merge Sort Implementation

void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int L[n1], R[n2];

    for(int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    // Merge the arrays back
    while(i < n1 && j < n2) {
        if(L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy remaining elements
    while(i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while(j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int left, int right) {
    if(left < right) {
        int mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Time Complexity:

• Best, Average, Worst: O(n log n)

Space Complexity: O(n)

Sparse Matrix

Definition: Matrix where most elements are zero.

Representation: Store only non-zero elements to save space.

3-Tuple Representation:

Row | Column | Value
----|--------|-------
 0  |   0    |   5
 1  |   2    |   8
 3  |   1    |   3

Implementation:

typedef struct {
    int row;
    int col;
    int value;
} Element;

typedef struct {
    int rows;
    int cols;
    int numNonZero;
    Element *elements;
} SparseMatrix;

SparseMatrix* createSparseMatrix(int rows, int cols, int numNonZero) {
    SparseMatrix *sm = (SparseMatrix*)malloc(sizeof(SparseMatrix));
    sm->rows = rows;
    sm->cols = cols;
    sm->numNonZero = numNonZero;
    sm->elements = (Element*)malloc(numNonZero * sizeof(Element));
    return sm;
}

void displaySparseMatrix(SparseMatrix *sm) {
    printf("Row\tCol\tValue\n");
    for(int i = 0; i < sm->numNonZero; i++) {
        printf("%d\t%d\t%d\n", 
               sm->elements[i].row, 
               sm->elements[i].col, 
               sm->elements[i].value);
    }
}

// Transpose of Sparse Matrix
SparseMatrix* transpose(SparseMatrix *sm) {
    SparseMatrix *result = createSparseMatrix(sm->cols, sm->rows, sm->numNonZero);

    int k = 0;
    for(int i = 0; i < sm->cols; i++) {
        for(int j = 0; j < sm->numNonZero; j++) {
            if(sm->elements[j].col == i) {
                result->elements[k].row = sm->elements[j].col;
                result->elements[k].col = sm->elements[j].row;
                result->elements[k].value = sm->elements[j].value;
                k++;
            }
        }
    }
    return result;
}

---

30. Classification of Sorting Algorithms

Based on Stability

Stable Sort: Maintains relative order of equal elements

• Bubble Sort, Insertion Sort, Merge Sort

Unstable Sort: May change relative order of equal elements

• Selection Sort, Quick Sort, Heap Sort

Based on Number of Swaps

Based on Number of Comparisons

Based on Complexity

O(n²) - Quadratic:

• Bubble Sort

• Selection Sort

• Insertion Sort

O(n log n) - Linearithmic:

• Merge Sort (always)

• Quick Sort (average)

• Heap Sort

O(n) - Linear:

• Counting Sort

• Radix Sort

• Bucket Sort (under certain conditions)

Based on Memory Usage

In-place (O(1) extra space):

• Bubble Sort

• Selection Sort

• Insertion Sort

• Quick Sort

Not in-place (O(n) extra space):

• Merge Sort

Based on Internal vs External

Internal: All data in main memory

• All comparison-based sorts

External: Data in secondary storage

• External Merge Sort

Comparison Table

---

31. Recursion & Stack in Recursion

Recursion

Definition: Function calling itself directly or indirectly.

Components:

1. Base Case: Termination condition

2. Recursive Case: Function calls itself with modified parameters

Example - Factorial:

int factorial(int n) {
    // Base case
    if(n == 0 || n == 1)
        return 1;

    // Recursive case
    return n * factorial(n - 1);
}

Example - Fibonacci:

int fibonacci(int n) {
    if(n <= 1)
        return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Stack in Recursion

How it works:

1. Each recursive call creates a new stack frame

2. Stack frame stores: local variables, parameters, return address

3. When base case reached, stack unwinds (LIFO)

Example: factorial(4)

Stack growth:

factorial(4)
  |
  v
factorial(4) -> factorial(3)
  |              |
  v              v
factorial(4) -> factorial(3) -> factorial(2)
  |              |                |
  v              v                v
factorial(4) -> factorial(3) -> factorial(2) -> factorial(1)
                                                   |
                                                   returns 1

Stack unwinding:
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Memory Layout:

Stack Frame for factorial(4):
---------------------------
| Return address          |
| Parameter: n = 4        |
| Local variables         |
---------------------------
Stack Frame for factorial(3):
---------------------------
| Return address          |
| Parameter: n = 3        |
| Local variables         |
---------------------------

---

32. Tower of Hanoi Problem

Problem: Move n disks from source rod to destination rod using auxiliary rod.

Rules:

1. Only one disk can be moved at a time

2. A larger disk cannot be placed on a smaller disk

3. Only the top disk of a stack can be moved

Recursive Solution:

void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    if(n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }

    // Move n-1 disks from source to auxiliary using destination
    towerOfHanoi(n - 1, source, auxiliary, destination);

    // Move nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);

    // Move n-1 disks from auxiliary to destination using source
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

// Usage
int main() {
    int n = 3;
    towerOfHanoi(n, 'A', 'C', 'B');
    // A = source, C = destination, B = auxiliary
    return 0;
}

Example with n=3:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Number of moves: 2ⁿ - 1

Time Complexity: O(2ⁿ)

---

33. Tree Terminology

Node: Basic unit containing data and pointers

Root: Topmost node (no parent)

Sibling: Nodes with same parent

Level: Distance from root (root is at level 0)

Leaf Node: Node with no children (terminal node)

Internal Node: Node with at least one child

Depth: Number of edges from root to node

Height: Number of edges from node to deepest leaf

Degree: Number of children of a node

Example:

         A          <- Root (Level 0)
        / \
       B   C        <- Level 1 (B and C are siblings)
      / \   \
     D   E   F      <- Level 2 (Leaf nodes: D, E, F)

• Root: A

• Siblings: B and C are siblings, D and E are siblings

• Level of D: 2

• Leaf nodes: D, E, F

• Internal nodes: A, B, C

• Degree of A: 2, Degree of B: 2, Degree of D: 0

• Height of tree: 2

---

34. Preorder and Postorder Traversal

Binary Tree Traversals

Given Tree:

       1
      / \
     2   3
    / \
   4   5

Preorder Traversal (Root-Left-Right)

Algorithm:

void preorder(Node *root) {
    if(root == NULL)
        return;

    printf("%d ", root->data);  // Visit root
    preorder(root->left);        // Traverse left
    preorder(root->right);       // Traverse right
}

Output: 1 2 4 5 3

Postorder Traversal (Left-Right-Root)

Algorithm:

void postorder(Node *root) {
    if(root == NULL)
        return;

    postorder(root->left);       // Traverse left
    postorder(root->right);      // Traverse right
    printf("%d ", root->data);   // Visit root
}

Output: 4 5 2 3 1

Inorder Traversal (Left-Root-Right)

void inorder(Node *root) {
    if(root == NULL)
        return;

    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

Output: 4 2 5 1 3

---

35. Binary Tree Operations & Types

Advantages of Trees

• Hierarchical structure representation

• Faster search than linked lists

• Dynamic size

• Efficient insertion and deletion

Disadvantages of Trees

• More complex than linear structures

• May become unbalanced

• More memory overhead (pointers)

Binary Tree Construction: 87,36,22,15,56,85,48,91,72,6

BST Insertion Order:

           87
          /  \
        36    91
       /  \
      22   56
     /  \    \
    15  85   72
   /   /
  6   48

Delete Nodes from BST

Case 1: Leaf Node (e.g., delete 6) Simply remove the node.

Case 2: One Child (e.g., delete 22) Replace node with its child.

Case 3: Two Children (e.g., delete 36) Replace with inorder successor (smallest in right subtree) or inorder predecessor (largest in left subtree).

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 {
        // Node with one child or no child
        if(root->left == NULL) {
            Node *temp = root->right;
            free(root);
            return temp;
        }
        else if(root->right == NULL) {
            Node *temp = root->left;
            free(root);
            return temp;
        }

        // Node with two children
        Node *temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

Types of Binary Trees

1. Complete Binary Tree:

• All levels completely filled except possibly last

• Last level filled from left to right

       1
      / \
     2   3
    / \  /
   4  5 6

2. Full Binary Tree:

• Every node has 0 or 2 children

       1
      / \
     2   3
    / \
   4   5

3. Strict Binary Tree (Proper Binary Tree):

• Same as Full Binary Tree

• Every node has exactly 0 or 2 children

4. Perfect Binary Tree:

• All internal nodes have 2 children

• All leaf nodes at same level

       1
      / \
     2   3
    / \ / \
   4  5 6  7

5. Threaded Binary Tree:

• NULL pointers are replaced with pointers to inorder predecessor/successor

• Faster traversal without recursion or stack

Single Threaded (Right threads):
    1
   / \
  2   3
   \
   (thread to 1)

Types of Threading:

• Single Threaded: Only right NULL pointers threaded

• Double Threaded: Both left and right NULL pointers threaded

---

36. Insert Element in Binary Tree

BST Insertion

Node* createNode(int data) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Node* insert(Node *root, int data) {
    if(root == NULL)
        return createNode(data);

    if(data < root->data)
        root->left = insert(root->left, data);
    else if(data > root->data)
        root->right = insert(root->right, data);

    return root;
}

// Usage
int main() {
    Node *root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);

    return 0;
}

Level Order Insertion (Complete Binary Tree)

void insertLevelOrder(Node **root, int data) {
    Node *newNode = createNode(data);

    if(*root == NULL) {
        *root = newNode;
        return;
    }

    // Use queue for level order traversal
    Node *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = *root;

    while(front < rear) {
        Node *temp = queue[front++];

        if(temp->left == NULL) {
            temp->left = newNode;
            return;
        } else {
            queue[rear++] = temp->left;
        }

        if(temp->right == NULL) {
            temp->right = newNode;
            return;
        } else {
            queue[rear++] = temp->right;
        }
    }
}

---

37. Selection Sort, Hashing

Selection Sort

Algorithm: Find minimum element and swap with first unsorted element.

void selectionSort(int arr[], int n) {
    for(int i = 0; i < n - 1; i++) {
        int minIndex = i;

        // Find minimum element in unsorted portion
        for(int j = i + 1; j < n; j++) {
            if(arr[j] < arr[minIndex])
                minIndex = j;
        }

        // Swap minimum with first unsorted element
        if(minIndex != i) {
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }
}

Time Complexity: O(n²) in all cases Space Complexity: O(1) Number of Swaps: O(n)

Hashing

Definition: Technique to map data to fixed-size values (hash codes) for fast access.

Hash Function: Converts key into array index.

Common Hash Functions:

1. Division Method:

int hash(int key, int tableSize) {
    return key % tableSize;
}

2. Multiplication Method:

int hash(int key, int tableSize) {
    float A = 0.618033; // (√5 - 1) / 2
    return (int)(tableSize * fmod(key * A, 1.0));
}

3. Mid-Square Method:

int hash(int key, int tableSize) {
    int square = key * key;
    // Extract middle digits
    return (square / 10) % tableSize;
}

4. Folding Method:

• Divide key into parts

• Add parts together

• Apply modulo

Hashing vs Searching

---

38. Collision Resolution Techniques

Collision: When two keys hash to same index.

1. Separate Chaining (Open Hashing)

Store colliding elements in linked list at each index.

typedef struct Node {
    int key;
    int value;
    struct Node *next;
} Node;

typedef struct {
    Node **table;
    int size;
} HashTable;

void insert(HashTable *ht, int key, int value) {
    int index = key % ht->size;

    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = ht->table[index];
    ht->table[index] = newNode;
}

int search(HashTable *ht, int key) {
    int index = key % ht->size;
    Node *temp = ht->table[index];

    while(temp != NULL) {
        if(temp->key == key)
            return temp->value;
        temp = temp->next;
    }
    return -1; // Not found
}

2. Open Addressing (Closed Hashing)

Store all elements in hash table itself.

a) Linear Probing:

h(k, i) = (h(k) + i) % m

Check next slot sequentially.

int linearProbe(int key, int i, int tableSize) {
    return (key + i) % tableSize;
}

void insertLinearProbing(int table[], int key, int tableSize) {
    int index = key % tableSize;
    int i = 0;

    while(table[(index + i) % tableSize] != -1) {
        i++;
        if(i == tableSize) {
            printf("Table full\n");
            return;
        }
    }
    table[(index + i) % tableSize] = key;
}

b) Quadratic Probing:

h(k, i) = (h(k) + c1*i + c2*i²) % m

int quadraticProbe(int key, int i, int tableSize) {
    return (key + i * i) % tableSize;
}

c) Double Hashing:

h(k, i) = (h1(k) + i * h2(k)) % m

int doubleHash(int key, int i, int tableSize) {
    int h1 = key % tableSize;
    int h2 = 7 - (key % 7); // Second hash function
    return (h1 + i * h2) % tableSize;
}

Comparison of Collision Techniques

---

39. General Tree vs Binary Tree

General Tree:

       A
     / | \
    B  C  D
   /|  |
  E F  G

Binary Tree:

       A
      / \
     B   C
    / \
   D   E

---

40. Recursive Binary Search & ADT

Recursive Binary Search

int binarySearchRecursive(int arr[], int low, int high, int key) {
    if(low > high)
        return -1; // Not found

    int mid = low + (high - low) / 2;

    if(arr[mid] == key)
        return mid; // Found

    if(arr[mid] > key)
        return binarySearchRecursive(arr, low, mid - 1, key);
    else
        return binarySearchRecursive(arr, mid + 1, high, key);
}

// Usage
int main() {
    int arr[] = {2, 5, 8, 12, 16, 23, 38, 45, 56, 67, 78};
    int n = 11;
    int key = 23;

    int result = binarySearchRecursive(arr, 0, n - 1, key);

    if(result != -1)
        printf("Element found at index %d\n", result);
    else
        printf("Element not found\n");

    return 0;
}

Recurrence Relation: T(n) = T(n/2) + c

Time Complexity: O(log n) Space Complexity: O(log n) - recursion stack

Abstract Data Type (ADT)

Definition: A data type defined by its behavior (operations) rather than implementation.

Components:

1. Data: Values that can be stored

2. Operations: Functions that can be performed

3. Error Conditions: Exceptional situations

Example - Stack ADT:

Data: Collection of elements
Operations:
  - push(element): Add element to top
  - pop(): Remove and return top element
  - peek(): Return top element without removing
  - isEmpty(): Check if stack is empty
  - isFull(): Check if stack is full

Example - Queue ADT:

Data: Collection of elements
Operations:
  - enqueue(element): Add element to rear
  - dequeue(): Remove and return front element
  - front(): Return front element
  - isEmpty(): Check if queue is empty
  - isFull(): Check if queue is full

Benefits of ADT:

• Abstraction: Hide implementation details

• Modularity: Changes don't affect users

• Flexibility: Multiple implementations possible

• Reusability: Can be used in different programs

---

Quick Reference Summary

Time Complexities

• Binary Search: O(log n)

• Linear Search: O(n)

• Bubble/Selection/Insertion Sort: O(n²)

• Merge/Quick/Heap Sort: O(n log n)

• Hashing: O(1) average

Space Complexities

• Array/Stack/Queue: O(n)

• Linked List: O(n)

• Recursion: O(n) stack space

• In-place sorts: O(1)

Important Formulas

• 2D Array Row Major: Address = Base + [(i × n) + j] × size

• 2D Array Column Major: Address = Base + [(j × m) + i] × size

• Tower of Hanoi: 2ⁿ - 1 moves

• AVL Balance Factor: Height(Left) - Height(Right)

---