DSA · CSE205
Data Structures &
Algorithms
Code Reference
10 high-yield programs for the written & coding exam —
exact syntax, complexity notes, and common mistakes to
avoid when writing code by hand.
CONTENTS
01 Binary Search
02 Insertion Sort
03 Singly Linked List \u2014 Insert & Delete
04 Stack (Array) \u2014 Balanced Parentheses
05 Circular Queue (Array)
06 Tower of Hanoi (Recursive)
07 BST \u2014 Insert & Traversals
08 Merge Sort (Recursive)
09 Quick Sort (Recursive)
10 Heap Sort
ANANDITA CHAKRABORTY · 12324876 CSE205 · PREPARED WITH CLAUDE
01 Binary Search
Time: O(log n) | Space: O(1) | Precondition: array must be sorted
#include <iostream>
using namespace std;
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key) return mid;
else if (arr[mid] < key) low = mid + 1;
else high = mid - 1;
}
return -1;
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12};
int n = 6, key = 8;
int result = binarySearch(arr, n, key);
if (result != -1) cout << "Found at index " << result;
else cout << "Not found";
return 0;
}
02 Insertion Sort
Best: O(n) | Worst/Avg: O(n²) | Stable: Yes
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main() {
int arr[] = {9, 5, 1, 4, 3};
int n = 5;
insertionSort(arr, n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
03 Singly Linked List \u2014 Insert & Delete
Insert at end: O(n) | Delete: O(n)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* head = NULL;
void insertAtEnd(int val) {
Node* newNode = new Node();
newNode->data = val;
newNode->next = NULL;
if (head == NULL) { head = newNode; return; }
Node* temp = head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
}
void deleteNode(int val) {
if (head == NULL) return;
if (head->data == val) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* curr = head;
while (curr->next != NULL && curr->next->data != val)
curr = curr->next;
if (curr->next != NULL) {
Node* temp = curr->next;
curr->next = curr->next->next;
delete temp;
}
}
void display() {
Node* temp = head;
while (temp != NULL) {
cout << temp->data << " -> ";
temp = temp->next;
}
cout << "NULL" << endl;
}
int main() {
insertAtEnd(10);
insertAtEnd(20);
insertAtEnd(30);
display();
deleteNode(20);
display();
return 0;
}
04 Stack (Array) \u2014 Balanced Parentheses
Time: O(n) | Space: O(n)
#include <iostream>
using namespace std;
#define MAX 100
class Stack {
int arr[MAX];
int top;
public:
Stack() { top = -1; }
void push(int val) {
if (top == MAX - 1) { cout << "Overflow"; return; }
arr[++top] = val;
}
int pop() {
if (top == -1) { cout << "Underflow"; return -1; }
return arr[top--];
}
bool isEmpty() { return top == -1; }
};
bool isBalanced(string expr) {
Stack s;
for (char ch : expr) {
if (ch == '(' || ch == '{' || ch == '[')
[Link](ch);
else if (ch == ')' || ch == '}' || ch == ']') {
if ([Link]()) return false;
char top = [Link]();
if ((ch == ')' && top != '(') ||
(ch == '}' && top != '{') ||
(ch == ']' && top != '['))
return false;
}
}
return [Link]();
}
int main() {
string expr = "{[()]}";
if (isBalanced(expr)) cout << "Balanced";
else cout << "Not Balanced";
return 0;
}
05 Circular Queue (Array)
Enqueue/Dequeue: O(1)
#include <iostream>
using namespace std;
#define SIZE 5
class CircularQueue {
int arr[SIZE];
int front, rear;
public:
CircularQueue() { front = rear = -1; }
void enqueue(int val) {
if ((rear + 1) % SIZE == front) { cout << "Full"; return; }
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
arr[rear] = val;
}
int dequeue() {
if (front == -1) { cout << "Empty"; return -1; }
int val = arr[front];
if (front == rear) front = rear = -1;
else front = (front + 1) % SIZE;
return val;
}
};
int main() {
CircularQueue q;
[Link](1);
[Link](2);
[Link](3);
cout << [Link]() << endl;
cout << [Link]() << endl;
return 0;
}
06 Tower of Hanoi (Recursive)
Time: O(2n)
#include <iostream>
using namespace std;
void towerOfHanoi(int n, char from, char aux, char to) {
if (n == 0) return;
towerOfHanoi(n - 1, from, to, aux);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
towerOfHanoi(n - 1, aux, from, to);
}
int main() {
int n = 3;
towerOfHanoi(n, 'A', 'B', 'C');
return 0;
}
07 BST \u2014 Insert & Traversals
Insert/Search: O(log n) avg, O(n) worst | Traversal: O(n)
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* createNode(int val) {
Node* newNode = new Node();
newNode->data = val;
newNode->left = newNode->right = NULL;
return newNode;
}
Node* insert(Node* root, int val) {
if (root == NULL) return createNode(val);
if (val < root->data) root->left = insert(root->left, val);
else if (val > root->data) root->right = insert(root->right, val);
return root;
}
void inorder(Node* root) {
if (root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
void preorder(Node* root) {
if (root == NULL) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
void postorder(Node* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
int main() {
Node* root = NULL;
int values[] = {50, 30, 70, 20, 40, 60, 80};
for (int v : values) root = insert(root, v);
cout << "Inorder: "; inorder(root); cout << endl;
cout << "Preorder: "; preorder(root); cout << endl;
cout << "Postorder: "; postorder(root); cout << endl;
return 0;
}
08 Merge Sort (Recursive)
Time: O(n log n) all cases | Stable: Yes | Space: O(n)
#include <iostream>
using namespace std;
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
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;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
void mergeSort(int arr[], int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;
mergeSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
09 Quick Sort (Recursive)
Avg: O(n log n) | Worst: O(n²) | In-place
#include <iostream>
using namespace std;
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], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
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);
quickSort(arr, pi + 1, high);
}
}
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++) cout << arr[i] << " ";
return 0;
}
10 Heap Sort
Build heap: O(n) | Heapify: O(log n) | Overall: O(n log n)
#include <iostream>
using namespace std;
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) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = 6;
heapSort(arr, n);
for (int i = 0; i < n; i++) cout << arr[i] << " ";
return 0;
}
Common Handwriting Mistakes
Things to double-check since there's no compiler to catch typos on paper
Missing semicolons after struct declarations and variable declarations
Forgetting the return type of a function, or mismatching void vs int
Using & incorrectly \u2014 arrays already decay to pointers, no & needed for arrays
Confusing -> vs . \u2014 pointers use -> , objects use .
Unbalanced braces { } \u2014 count them as you write
Forgetting NULL checks before dereferencing a pointer
Forgetting #include lines or using namespace std; at the top
Missing return 0; at the end of main()
END OF CODE REFERENCE · GOOD LUCK