# Complete DSA Notes for Sem 3 Exam

## 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:**

| Structure | Union |
| --- | --- |
| All members allocated separate memory | All members share same memory |
| Size = sum of all members | Size = largest member |
| Can access all members simultaneously | Can access only one member at a time |
| Keyword: `struct` | Keyword: `union` |

```c
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.

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

---

## 5\. Nested Structure

Structure inside another structure.

```c
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

```c
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

| Stack | Queue |
| --- | --- |
| LIFO (Last In First Out) | FIFO (First In First Out) |
| Insert and delete from one end (top) | Insert at rear, delete from front |
| One pointer (top) | Two pointers (front, rear) |
| Example: Browser back button | Example: Printer queue |

### B) AVL Tree vs BST

| AVL Tree | BST |
| --- | --- |
| Self-balancing BST | May be unbalanced |
| Height difference ≤ 1 | No height restriction |
| Faster search (O(log n) always) | Search can be O(n) worst case |
| More rotations needed | No rotations |

### C) Linear vs Binary Search

| Linear Search | Binary Search |
| --- | --- |
| Works on unsorted array | Requires sorted array |
| Time: O(n) | Time: O(log n) |
| Simple implementation | Complex implementation |
| No preprocessing | Array must be sorted |

### D) Array vs Linked List

| Array | Linked List |
| --- | --- |
| Fixed size | Dynamic size |
| Contiguous memory | Non-contiguous memory |
| Random access O(1) | Sequential access O(n) |
| No extra memory for pointers | Extra memory for pointers |
| Insertion/Deletion slow | Insertion/Deletion fast |

### E) Hashing vs Searching

| Hashing | Searching |
| --- | --- |
| Uses hash function | Uses comparison |
| Average O(1) access | O(log n) or O(n) |
| Requires hash table | Works on any structure |
| May have collisions | No collisions |

---

## 8\. Differences - Set B

### A) Linear vs Circular Queue

| Linear Queue | Circular Queue |
| --- | --- |
| Front and rear move forward only | Front and rear wrap around |
| Space wastage occurs | No space wastage |
| Rear reaches end even if space available | Uses all positions efficiently |
| Front = -1, Rear = -1 initially | Last position connects to first |

### B) Recursion vs Iteration

| Recursion | Iteration |
| --- | --- |
| Function calls itself | Uses loops |
| Uses system stack | No stack overhead |
| More memory | Less memory |
| Code is shorter | Code may be longer |
| Can be slow | Generally faster |
| Risk of stack overflow | No such risk |

### C) Internal vs External Sorting

| Internal Sorting | External Sorting |
| --- | --- |
| All data in main memory | Data in secondary storage |
| Faster | Slower |
| For small data | For large data |
| Example: Quick Sort | Example: Merge Sort on disk |

---

## 9\. Binary Search Implementation & Time Complexity

```c
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)

```c
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)

```c
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:**

```bash
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

```c
#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

```c
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:**

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

**Example:** A\[3\]\[4\]

```bash
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:**

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

**Example:** A\[3\]\[4\]

```bash
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)

```c
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)

```c
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

```c
#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

```c
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.

```c
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
    

```c
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
    

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

---

## 17\. Bubble Sort Implementation

```c
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

```c
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⁰

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

---

## 19\. Polynomial Addition Using Linked List

```c
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:**

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

**Insertion at End:**

```c
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:**

```c
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:**

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

**Reverse:**

```c
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:**

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

---

## 21\. Largest and Smallest Number Algorithm

```c
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 Memory Allocation | Dynamic Memory Allocation |
| --- | --- |
| Compile time allocation | Runtime allocation |
| Fixed size | Variable size |
| Uses stack | Uses heap |
| Automatic deallocation | Manual deallocation needed |
| Faster | Slower |
| Less flexible | More flexible |
| Example: `int arr[10];` | Example: `malloc(), calloc()` |

**Static Example:**

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

**Dynamic Example:**

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

---

## 23\. malloc() vs calloc()

| malloc() | calloc() |
| --- | --- |
| Allocates single block | Allocates multiple blocks |
| Memory not initialized | Memory initialized to zero |
| Faster | Slower (due to initialization) |
| Syntax: `malloc(size)` | Syntax: `calloc(n, size)` |

**malloc Example:**

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

**calloc Example:**

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

**realloc():**

```c
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:**

```bash
    z                      y
   /                      / \
  y        -->           x   z
 /
x
```

**2\. Right-Right (RR) Rotation:**

```bash
x                          y
 \                        / \
  y        -->           x   z
   \
    z
```

**3\. Left-Right (LR) Rotation:**

```bash
  z                z                  y
 /                /                  / \
y        -->     y        -->       x   z
 \              /
  x            x
```

**4\. Right-Left (RL) Rotation:**

```bash
x              x                    y
 \              \                  / \
  z      -->     y       -->      x   z
 /                \
y                  z
```

**C Implementation (LL Rotation):**

```c
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:**

```bash
8
```

**Insert 12:**

```bash
  8
   \
   12
```

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

```bash
  8              9
   \            / \
   12    -->   8  12
  /
 9
```

**Insert 11:**

```bash
    9
   / \
  8  12
     /
    11
```

**Insert 7:**

```bash
    9
   / \
  8  12
 /   /
7   11
```

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

```bash
      9
     / \
    7  12
   / \  /
  6  8 11
```

**Insert 66:**

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

**Insert 2:**

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

**Insert 1:** (Rebalancing needed)

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

**Insert 44:**

```bash
        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:**

```bash
       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:**

```bash
                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 &lt; pivot on left, &gt; pivot on right
    
3. Recursively sort left and right partitions
    

```c
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:**

```c
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

```c
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:**

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

**Implementation:**

```c
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

| Algorithm | Number of Swaps |
| --- | --- |
| Selection Sort | O(n) |
| Bubble Sort | O(n²) |
| Insertion Sort | O(n²) |
| Quick Sort | O(n log n) average |

### Based on Number of Comparisons

| Algorithm | Comparisons |
| --- | --- |
| Bubble Sort | O(n²) |
| Selection Sort | O(n²) |
| Insertion Sort | O(n²) |
| Merge Sort | O(n log n) |
| Quick Sort | O(n log n) average |

### 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

| Algorithm | Time (Best) | Time (Avg) | Time (Worst) | Space | Stable |
| --- | --- | --- | --- | --- | --- |
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |

---

## 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:**

```c
int factorial(int n) {
    // Base case
    if(n == 0 || n == 1)
        return 1;
    
    // Recursive case
    return n * factorial(n - 1);
}
```

**Example - Fibonacci:**

```c
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)**

```bash
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:**

```bash
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:**

```c
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:**

```bash
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:**

```bash
         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:**

```bash
       1
      / \
     2   3
    / \
   4   5
```

### Preorder Traversal (Root-Left-Right)

**Algorithm:**

```c
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:**

```c
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)

```c
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:**

```bash
           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).

```c
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
    

```bash
       1
      / \
     2   3
    / \  /
   4  5 6
```

**2\. Full Binary Tree:**

* Every node has 0 or 2 children
    

```bash
       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
    

```bash
       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
    

```bash
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

```c
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)

```c
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.

```c
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:**

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

**2\. Multiplication Method:**

```c
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:**

```c
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

| Hashing | Searching |
| --- | --- |
| O(1) average access | O(log n) or O(n) |
| Requires hash function | Uses comparisons |
| May have collisions | No collisions |
| Fixed table size initially | Works on any size |
| Best for key-value pairs | Best for ordered data |

---

## 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.

```c
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:**

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

Check next slot sequentially.

```c
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:**

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

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

**c) Double Hashing:**

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

```c
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

| Technique | Clustering | Performance | Space |
| --- | --- | --- | --- |
| Separate Chaining | No | Good | Extra for pointers |
| Linear Probing | Primary | Poor when full | No extra |
| Quadratic Probing | Secondary | Better | No extra |
| Double Hashing | Minimal | Best | No extra |

---

## 39\. General Tree vs Binary Tree

| General Tree | Binary Tree |
| --- | --- |
| Node can have any number of children | Node has max 2 children |
| No specific ordering | Left and right child distinction |
| More complex traversal | Simple traversal algorithms |
| Example: File system | Example: Expression tree |
| More memory per node | Fixed memory (2 pointers) |

**General Tree:**

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

**Binary Tree:**

```bash
       A
      / \
     B   C
    / \
   D   E
```

---

## 40\. Recursive Binary Search & ADT

### Recursive Binary Search

```c
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:**

```bash
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:**

```bash
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)
    

---