Select a file from the list to view it.
01-binary-search-trees/README.md
# Binary search trees
These programs build binary search trees and practice ways to visit or inspect the nodes.
- [a-tree-cycle-check.cpp](a-tree-cycle-check.cpp) inserts values into a tree. The `hasCycle()` function currently returns `false` without checking for a cycle, so this is not a working cycle detector.
- [level-order-and-node-queries.cpp](level-order-and-node-queries.cpp) prints nodes by level and reports leaves, parents, siblings, and subtree roots.
- [mirror-tree.cpp](mirror-tree.cpp) swaps the left and right children recursively.
- [sibling-nodes.cpp](sibling-nodes.cpp) finds nodes that share a parent.
- [inorder-traversal.cpp](inorder-traversal.cpp) and [inorder-traversal-example-2.cpp](inorder-traversal-example-2.cpp) print values using inorder traversal.
- [postorder-traversal.cpp](postorder-traversal.cpp) and [postorder-traversal-example-2.cpp](postorder-traversal-example-2.cpp) use postorder traversal.
- [preorder-traversal.cpp](preorder-traversal.cpp) and [preorder-traversal-example-2.cpp](preorder-traversal-example-2.cpp) use preorder traversal.
- [preorder-tree.cpp](preorder-tree.cpp) builds a tree and prints it in preorder.
- [check-tree-balance.cpp](check-tree-balance.cpp) checks height balance; it does not rebalance the tree.
- [print-leaf-nodes.cpp](print-leaf-nodes.cpp) prints nodes that have no children.
01-binary-search-trees/a-tree-cycle-check.cpp
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int num) {
data = num;
left = right = NULL;
}
};
class tree {
node* root;
public:
tree() {
root = NULL;
}
void enternode(int val) {
root = insert(root, val);
}
node* insert(node* temp, int val) {
if (temp == NULL)
return new node(val);
if (val < temp->data)
temp->left = insert(temp->left, val);
else
temp->right = insert(temp->right, val);
return temp;
}
bool hasCycle() {
return false; // No way to detect cycles without tracking visited pointers
}
};
int main() {
tree t;
int n, val;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> val;
t.enternode(val);
}
if (t.hasCycle())
cout << "Cycle detected in the tree." << endl;
else
cout << "No cycle found. The tree is safe." << endl;
return 0;
}
01-binary-search-trees/check-tree-balance.cpp
// Wheather a tree is balanced
#include<iostream>
#include<cmath>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int num) {
data = num;
left = right = NULL;
}
};
class tree {
node* root;
public:
tree() {
root = NULL;
}
void enternode(int val) {
root = insert(root, val);
}
node* insert(node* temp, int val) {
if (temp == NULL)
return new node(val);
if (val < temp->data)
temp->left = insert(temp->left, val);
else
temp->right = insert(temp->right, val);
return temp;
}
int checkHeight(node* temp, bool& isBalanced) {
if (temp == NULL)
return 0;
int leftHeight = checkHeight(temp->left, isBalanced);
int rightHeight = checkHeight(temp->right, isBalanced);
if (abs(leftHeight - rightHeight) > 1)
isBalanced = false;
return max(leftHeight, rightHeight) + 1;
}
bool isTreeBalanced() {
bool isBalanced = true;
checkHeight(root, isBalanced);
return isBalanced;
}
void inorder(node* temp) {
if (temp == NULL)
return;
inorder(temp->left);
cout << temp->data << " ";
inorder(temp->right);
}
void display() {
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
}
};
int main() {
tree t;
int n, val;
cout<<"Enter Number of Node you wnat to enter:";
cin >> n;
for (int i = 0; i < n; i++) {
cin >> val;
t.enternode(val);
}
t.display();
if (t.isTreeBalanced())
cout << "The tree is balanced." << endl;
else
cout << "The tree is NOT balanced." << endl;
return 0;
}
01-binary-search-trees/inorder-traversal-example-2.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void in_o(node* r) {
if (r == NULL) return;
in_o(r->left);
cout << r->d << " ";
in_o(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Inorder traversal: ";
c.in_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/inorder-traversal.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void in_o(node* r) {
if (r == NULL) return;
in_o(r->left);
cout << r->d << " ";
in_o(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Inorder traversal: ";
c.in_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/level-order-and-node-queries.cpp
#include<iostream>
#include<queue>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
class tree {
int a[100]; // increased array size for more flexibility
int i = 0, c = 0;
public:
node* insert(node* root, int val) {
if (root == NULL) {
return new node(val);
}
if (val < root->data) {
root->left = insert(root->left, val);
} else {
root->right = insert(root->right, val);
}
return root;
}
void display_level(node* root) {
queue<node*> q;
int l = 0;
if (root == NULL) return;
q.push(root);
q.push(NULL);
while (!q.empty()) {
node* curr = q.front();
q.pop();
if (curr == NULL) {
if (!q.empty()) {
cout << endl;
q.push(NULL);
l++;
continue;
} else {
l++;
break;
}
}
cout << curr->data << " ";
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
cout << "\n\nHeight of tree is: " << l << endl;
}
void cout_leafs(node* root) {
if (root == NULL) return;
if (root->left == NULL && root->right == NULL) {
a[i++] = root->data;
c++;
}
cout_leafs(root->left);
cout_leafs(root->right);
}
void display_leafs() {
cout << "\nTotal leaf nodes: " << c << endl;
cout << "Leaf nodes: ";
for (int j = 0; j < i; j++) {
cout << a[j] << " ";
}
cout << endl;
i = c = 0;
}
void count_parents(node* root) {
if (root == NULL) return;
if (root->left != NULL || root->right != NULL) {
a[i++] = root->data;
c++;
}
count_parents(root->left);
count_parents(root->right);
}
void display_parents() {
cout << "\nTotal parent nodes: " << c << endl;
cout << "Parent nodes: ";
for (int j = 0; j < i; j++) {
cout << a[j] << " ";
}
cout << endl;
i = c = 0;
}
void siblings(node* root) {
if (root == NULL) return;
if (root->left != NULL || root->right != NULL) {
cout << "\nParent: " << root->data << " => Children: ";
if (root->left) cout << root->left->data << " ";
if (root->right) cout << root->right->data << " ";
}
siblings(root->left);
siblings(root->right);
}
void count_sub_trees(node* root) {
static int s = -1;
if (root == NULL) return;
if (s != -1) {
a[i++] = root->data;
c++;
}
s++;
count_sub_trees(root->left);
count_sub_trees(root->right);
}
void display_sub_trees() {
cout << "\nTotal subtrees (excluding root): " << c << endl;
cout << "Subtree roots: ";
for (int j = 0; j < i; j++) {
cout << a[j] << " ";
}
cout << endl;
i = c = 0;
}
};
int main() {
tree t;
node* root = NULL;
int n, val;
cout << "Enter number of nodes to insert in BST: ";
cin >> n;
cout << "Enter " << n << " integers:\n";
for (int i = 0; i < n; i++) {
cin >> val;
root = t.insert(root, val);
}
cout << "\nLevel Order Traversal:\n";
t.display_level(root);
t.cout_leafs(root);
t.display_leafs();
t.count_parents(root);
t.display_parents();
t.siblings(root);
t.count_sub_trees(root);
t.display_sub_trees();
return 0;
}
01-binary-search-trees/mirror-tree.cpp
//Mirror of tree
#include<iostream>
using namespace std;
class node {
public:
node* right;
int data;
node* left;
node(int num) {
data = num;
right = left = NULL;
}
};
class tree {
node* root;
public:
tree() {
root = NULL;
}
void enternode(int num) {
root = insert(root, num);
}
node* insert(node* temp, int num) {
if (temp == NULL)
return new node(num);
if (num < temp->data)
temp->left = insert(temp->left, num);
else
temp->right = insert(temp->right, num);
return temp;
}
void mirrorTree() {
mirror(root);
}
void mirror(node* temp) {
if (temp == NULL)
return;
node* swap = temp->left;
temp->left = temp->right;
temp->right = swap;
mirror(temp->left);
mirror(temp->right);
}
void inorder(node* temp) {
if (temp == NULL)
return;
inorder(temp->left);
cout << temp->data << " ";
inorder(temp->right);
}
void display() {
cout << "Inorder Traversal: ";
inorder(root);
cout << endl;
}
};
int main() {
tree t;
int n, val;
cout << "How many nodes do you want to enter? ";
cin >> n;
cout << "Enter " << n << " values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
t.enternode(val);
}
cout << "\nOriginal Tree: ";
t.display();
t.mirrorTree();
cout << "Mirrored Tree: ";
t.display();
return 0;
}
01-binary-search-trees/postorder-traversal-example-2.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void post_o(node* r) {
if (r == NULL) return;
post_o(r->left);
post_o(r->right);
cout << r->d << " ";
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Postorder traversal: ";
c.post_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/postorder-traversal.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void post_o(node* r) {
if (r == NULL) return;
post_o(r->left);
post_o(r->right);
cout << r->d << " ";
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Postorder traversal: ";
c.post_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/preorder-traversal-example-2.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void pre_o(node* r) {
if (r == NULL) return;
cout << r->d << " ";
pre_o(r->left);
pre_o(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Preorder traversal: ";
c.pre_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/preorder-traversal.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void pre_o(node* r) {
if (r == NULL) return;
cout << r->d << " ";
pre_o(r->left);
pre_o(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Preorder traversal: ";
c.pre_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/preorder-tree.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int d) {
this->d = d;
left = right = NULL;
}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL) {
return new node(v);
}
if (v < r->d) {
r->left = insert(r->left, v);
} else if (v > r->d) {
r->right = insert(r->right, v);
}
return r;
}
void pre_o(node* r) {
if (r == NULL) return;
cout << r->d << " ";
pre_o(r->left);
pre_o(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values do you want to insert? ";
cin >> n;
cout << "Enter " << n << " integer values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Preorder traversal of the tree: ";
c.pre_o(r);
cout << endl;
return 0;
}
01-binary-search-trees/print-leaf-nodes.cpp
//write a cpp program that prints only the leaf nodes in a tree
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL) {
return new node(v);
}
if (v < r->d) {
r->left = insert(r->left, v);
} else if (v > r->d) {
r->right = insert(r->right, v);
}
return r;
}
void printLeafNodes(node* r) {
if (r == NULL) return;
if (r->left == NULL && r->right == NULL) {
cout << r->d << " ";
return;
}
printLeafNodes(r->left);
printLeafNodes(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Leaf nodes: ";
c.printLeafNodes(r);
cout << endl;
return 0;
}
01-binary-search-trees/sibling-nodes.cpp
#include<iostream>
using namespace std;
class node {
public:
int d;
node *left, *right;
node(int val) : d(val), left(NULL), right(NULL) {}
};
class B {
public:
node* insert(node* r, int v) {
if (r == NULL){
return new node(v);
}
if (v < r->d){
r->left = insert(r->left, v);
}
else if (v > r->d){
r->right = insert(r->right, v);
}
return r;
}
void in_o(node* r) {
if (r == NULL) return;
in_o(r->left);
cout << r->d << " ";
in_o(r->right);
}
void printSiblings(node* r) {
if (r == NULL) return;
// If both left and right child exist, they are siblings
if (r->left != NULL && r->right != NULL) {
cout << "Siblings: " << r->left->d << " and " << r->right->d << endl;
}
// Recurse on left and right subtree
printSiblings(r->left);
printSiblings(r->right);
}
};
int main() {
node *r = NULL;
B c;
int n, val;
cout << "How many values? ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; ++i) {
cin >> val;
r = c.insert(r, val);
}
cout << "Inorder traversal: ";
c.in_o(r);
cout << endl;
cout << "\nSibling nodes in the tree:\n";
c.printSiblings(r);
return 0;
}
02-avl-trees/README.md
# AVL trees
Both programs insert values into an AVL tree and use rotations when the tree becomes unbalanced. One prints an inorder traversal; the other prints preorder.
- [avl-tree-inorder.cpp](avl-tree-inorder.cpp)
- [avl-tree-preorder.cpp](avl-tree-preorder.cpp)
02-avl-trees/avl-tree-inorder.cpp
#include<iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
int height;
node(int val) {
data = val;
left = right = NULL;
height = 1;
}
};
int getHeight(node* n) {
return n ? n->height : 0;
}
int getBalance(node* n) {
return n ? getHeight(n->left) - getHeight(n->right) : 0;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
node* rotateRight(node* y) {
node* x = y->left;
node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
node* rotateLeft(node* x) {
node* y = x->right;
node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
node* insert(node* root, int key) {
if (root == NULL)
return new node(key);
if (key < root->data)
root->left = insert(root->left, key);
else if (key > root->data)
root->right = insert(root->right, key);
else
return root;
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int balance = getBalance(root);
if (balance > 1 && key < root->left->data)
return rotateRight(root);
if (balance < -1 && key > root->right->data)
return rotateLeft(root);
if (balance > 1 && key > root->left->data) {
root->left = rotateLeft(root->left);
return rotateRight(root);
}
if (balance < -1 && key < root->right->data) {
root->right = rotateRight(root->right);
return rotateLeft(root);
}
return root;
}
void inorder(node* root) {
if (root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
int main() {
node* root = NULL;
int n, val;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> val;
root = insert(root, val);
}
cout << "Inorder Traversal of AVL Tree: ";
inorder(root);
cout << endl;
return 0;
}
02-avl-trees/avl-tree-preorder.cpp
#include <iostream>
using namespace std;
class Node {
public:
int key, height;
Node* left;
Node* right;
Node(int val) {
key = val;
height = 1;
left = right = NULL;
}
};
int height(Node* n) {
return n ? n->height : 0;
}
int getBalance(Node* n) {
return n ? height(n->left) - height(n->right) : 0;
}
Node* rightRotate(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
return x;
}
Node* leftRotate(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
return y;
}
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node;
node->height = 1 + max(height(node->left), height(node->right));
int balance = getBalance(node);
if (balance > 1 && key < node->left->key)
return rightRotate(node);
if (balance < -1 && key > node->right->key)
return leftRotate(node);
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preorder(Node* root) {
if (root) {
cout << root->key << " ";
preorder(root->left);
preorder(root->right);
}
}
int main() {
Node* root = NULL;
int n, val;
cout << "Enter number of nodes to insert: ";
cin >> n;
cout << "Enter " << n << " values:\n";
for (int i = 0; i < n; i++) {
cin >> val;
root = insert(root, val);
}
cout << "Preorder traversal of AVL tree:\n";
preorder(root);
cout << endl;
return 0;
}
03-linked-lists/README.md
# Linked lists
These examples use linked nodes to store and move through information.
- [account-transaction-records.cpp](account-transaction-records.cpp) stores accounts and transaction records in linked lists.
- [song-playlist.cpp](song-playlist.cpp) uses a doubly linked list to move between songs.
- [browser-history.cpp](browser-history.cpp) moves forward and backward through a list of website names.
- [singly-linked-list.py](singly-linked-list.py) adds, inserts, deletes, and displays values in a singly linked list.
03-linked-lists/account-transaction-records.cpp
#include <iostream>
#include <string>
using namespace std;
struct transation {
int transaction_ID = 1;
string type;
int purchase;
transation* next;
transation* prv;
};
struct accounts {
int acc_id = 1;
string user_name;
accounts* next;
transation* head;
accounts* prv;
};
class tran {
public:
void insertinlink(transation*& head) {
char ck;
do {
int purchase;
string tp;
cout << "\nEnter Purchase: ";
cin >> purchase;
cin.ignore();
cout << "\nEnter Note: ";
getline(cin, tp);
transation* node = new transation();
node->purchase = purchase;
node->type = tp;
if (head) {
transation* temp = head;
while (temp->next) {
temp = temp->next;
}
node->transaction_ID = temp->transaction_ID + 1;
temp->next = node;
node->prv = temp;
} else {
head = node;
}
node->next = NULL;
cout << "\nPress 'Y' to enter another transaction: ";
cin >> ck;
} while (ck == 'Y' || ck == 'y');
}
void searchtran(transation* head) {
transation* temp = head;
while (temp) {
cout << "\nTransaction ID: " << temp->transaction_ID << endl;
cout << "Purchase: " << temp->purchase << endl;
cout << "Note: " << temp->type << endl;
temp = temp->next;
}
}
void totaltransations(transation* head) {
transation* temp = head;
int sum = 0;
while (temp) {
sum += temp->purchase;
temp = temp->next;
}
cout << "\nThe Total amount you have spent is: " << sum << " Rs\n";
}
void display(transation* head) {
transation* temp = head;
while (temp) {
cout << "\nTransaction ID: " << temp->transaction_ID << endl;
cout << "Purchase: " << temp->purchase << endl;
cout << "Note: " << temp->type << endl;
temp = temp->next;
}
}
};
class record {
accounts* acc_head;
int count = 0;
public:
record() {
acc_head = NULL;
}
void newaccount() {
string name;
cout << "\nEnter Name: ";
cin.ignore();
getline(cin, name);
accounts* acc = new accounts();
count++;
if (acc_head) {
accounts* temp = acc_head;
while (temp->next) {
temp = temp->next;
}
acc->acc_id = temp->acc_id + 1;
temp->next = acc;
acc->prv = temp;
} else {
acc_head = acc;
acc->prv = NULL;
}
cout << "\nYour Account ID is: " << acc->acc_id << endl;
acc->user_name = name;
acc->next = NULL;
acc->head = NULL;
tran chain;
chain.insertinlink(acc->head);
}
void searchaccount() {
int acid, attempts = 3;
string pn;
while (attempts > 0) {
cout << endl << "Enter Name: ";
cin.ignore();
getline(cin, pn);
cout << endl << "Enter Account ID: ";
cin >> acid;
accounts* temp = acc_head;
while (temp) {
if (pn == temp->user_name && acid == temp->acc_id) {
cout << "\n \t Transaction records\n\n";
tran temp1;
temp1.searchtran(temp->head);
return;
}
temp = temp->next;
}
attempts--;
if (attempts > 0) {
cout << endl << "Invalid ID or Name! Attempts left: " << attempts << endl;
} else {
cout << endl << "Access limit reached! Returning to menu..." << endl;
}
}
}
void addtoaccount() {
int acid, attempts = 3;
string pn;
while (attempts > 0) {
cout << endl << "Enter Name: ";
cin.ignore();
getline(cin, pn);
cout << endl << "Enter Account ID: ";
cin >> acid;
accounts* temp = acc_head;
while (temp) {
if (pn == temp->user_name && acid == temp->acc_id) {
tran temp1;
temp1.insertinlink(temp->head);
return;
}
temp = temp->next;
}
attempts--;
if (attempts > 0) {
cout << endl << "Invalid ID or Name! Attempts left: " << attempts << endl;
} else {
cout << endl << "Access limit reached! Returning to menu..." << endl;
}
}
}
int totalacc() {
return count;
}
void totalexpense() {
int acid, attempts = 3;
string pn;
while (attempts > 0) {
cout << endl << "Enter Name: ";
cin.ignore();
getline(cin, pn);
cout << endl << "Enter Account ID: ";
cin >> acid;
accounts* temp = acc_head;
while (temp) {
if (pn == temp->user_name && acid == temp->acc_id) {
tran temp1;
temp1.totaltransations(temp->head);
return;
}
temp = temp->next;
}
attempts--;
if (attempts > 0) {
cout << endl << "Invalid ID or Name! Attempts left: " << attempts << endl;
} else {
cout << endl << "Access limit reached! Returning to menu..." << endl;
}
}
}
void display() {
accounts* temp = acc_head;
while (temp) {
cout << "\nName: " << temp->user_name << endl;
cout << "Account ID: " << temp->acc_id << endl;
char ans;
cout << "\nPress 'Y' if you want transaction details: ";
cin >> ans;
if (ans == 'y' || ans == 'Y') {
tran temp1;
temp1.display(temp->head);
}
temp = temp->next;
}
}
};
int main() {
int a, pass = 1234, p;
record m;
while (true) {
cout << "\t\tMenu\n";
cout << endl << "1. New Account.";
cout << endl << "2. Search Account.";
cout << endl << "3. Add Transaction to Existing Account.";
cout << endl << "4. Display Number of Accounts.";
cout << endl << "5. Total Transactions of an Account.";
cout << endl << "6. Display All Accounts.";
cout << endl << "7. Exit.";
cout << endl << "\nEnter choice: ";
cin >> a;
switch (a) {
case 1:
m.newaccount();
break;
case 2:
m.searchaccount();
break;
case 3:
m.addtoaccount();
break;
case 4:
cout << "\nTotal accounts are: " << m.totalacc() << endl;
break;
case 5:
m.totalexpense();
break;
case 6:
cout << "Enter Password: ";
cin >> p;
if (pass == p) m.display();
else cout << "\nInvalid password!\n";
break;
case 7:
return 0;
default: cout << "\nInvalid choice! Try again.\n";
}
}
}
03-linked-lists/browser-history.cpp
#include<iostream>
using namespace std;
class website {
public:
website* next;
string WebName;
website* prev;
website() {
next = NULL;
WebName = "";
prev = NULL;
}
};
class browser {
private:
website* head;
website* recent;
public:
browser() {
head = NULL;
recent = NULL;
}
void search() {
website* domain = new website();
cout << "\nEnter Website you want to search: ";
cin >> domain->WebName;
cout << "\n" << domain->WebName << " is essential for nowadays. \n";
if (head == NULL) {
domain->next = NULL;
domain->prev = NULL;
head = domain;
recent = domain;
return;
}
website* temp = head;
while (temp->next) {
temp = temp->next;
}
domain->prev = temp;
temp->next = domain;
recent = domain;
}
void history() {
if (recent == NULL) {
cout << "\nNo history available.\n";
return;
}
website* temp = recent;
cout << "\nBrowsing History:\n";
while (temp != NULL) {
cout << temp->WebName << "\n";
temp = temp->prev;
}
}
void forward() {
if (recent == NULL || recent->next == NULL) {
cout << "\nThere is no Next Tab\n";
return;
}
recent = recent->next;
cout << "\nThe Next Tab: " << recent->WebName << endl;
}
void previous() {
if (recent == NULL || recent->prev == NULL) {
cout << "\nThere is no Previous Tab\n";
return;
}
recent = recent->prev;
cout << "\nThe Previous Tab: " << recent->WebName << endl;
}
void deletehistory() {
if (head == NULL) {
cout << "\nHistory is empty.\n";
return;
}
int pos;
cout << "Enter the position to delete (1-based index): ";
cin >> pos;
website* temp = head;
int count = 1;
while (temp != NULL && count < pos) {
temp = temp->next;
count++;
}
if (temp == NULL) {
cout << "\nInvalid position.\n";
return;
}
if (temp == recent) {
if (temp->prev)
recent = temp->prev;
else if (temp->next)
recent = temp->next;
else
recent = NULL;
}
if (temp == head) {
head = temp->next;
if (head)
head->prev = NULL;
} else {
temp->prev->next = temp->next;
}
if (temp->next)
temp->next->prev = temp->prev;
cout << "\nDeleted: " << temp->WebName << endl;
delete temp;
}
};
int main() {
browser google;
int n = 0;
do {
cout << "\n-----MENU-----\n";
cout << "1. Browse a Website\n";
cout << "2. Show History\n";
cout << "3. Forward Tab\n";
cout << "4. Previous Tab\n";
cout << "5. Delete History at Position\n";
cout << "6. Exit\n";
cout << "Choose Option: ";
cin >> n;
switch (n) {
case 1:
google.search();
break;
case 2:
google.history();
break;
case 3:
google.forward();
break;
case 4:
google.previous();
break;
case 5:
google.deletehistory();
break;
case 6:
cout << "\nExiting browser...\n";
break;
default:
cout << "\nInvalid Choice!\n";
break;
}
} while (n != 6);
return 0;
}
03-linked-lists/singly-linked-list.py
class Node:
"""
A class representing a node in a singly linked list.
"""
def __init__(self, data):
self.data = data
self.next = None
class SinglyLinkedList:
"""
A class to manage a singly linked list.
"""
def __init__(self):
self.head = None
def insert_at_end(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
return
curr = self.head
while curr.next:
curr = curr.next
curr.next = new_node
def insert_at_beginning(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert_after_value(self, target, data):
curr = self.head
while curr:
if curr.data == target:
new_node = Node(data)
new_node.next = curr.next
curr.next = new_node
return
curr = curr.next
raise ValueError(f"Value '{target}' not found.")
def delete_value(self, target):
if not self.head:
raise ValueError("List is empty.")
if self.head.data == target:
self.head = self.head.next
return
curr = self.head
while curr.next:
if curr.next.data == target:
curr.next = curr.next.next
return
curr = curr.next
raise ValueError(f"Value '{target}' not found.")
def traverse(self):
elements = []
curr = self.head
while curr:
elements.append(curr.data)
curr = curr.next
return elements
def __str__(self):
return " -> ".join(map(str, self.traverse())) + " -> None"
# === Main program with user interaction ===
def main():
ll = SinglyLinkedList()
while True:
print("\n--- Singly Linked List Menu ---")
print("1. Insert at beginning")
print("2. Insert at end")
print("3. Insert after value")
print("4. Delete a value")
print("5. Display list")
print("6. Exit")
choice = input("Enter your choice (1-6): ")
try:
if choice == '1':
val = input("Enter value to insert at beginning: ")
ll.insert_at_beginning(val)
elif choice == '2':
val = input("Enter value to insert at end: ")
ll.insert_at_end(val)
elif choice == '3':
target = input("Enter the value after which to insert: ")
val = input("Enter value to insert: ")
ll.insert_after_value(target, val)
elif choice == '4':
val = input("Enter value to delete: ")
ll.delete_value(val)
elif choice == '5':
print("Linked List:")
print(ll)
elif choice == '6':
print("Exiting program.")
break
else:
print("Invalid choice. Please enter a number between 1 and 6.")
except ValueError as ve:
print(f"Error: {ve}")
if __name__ == "__main__":
main()
1
03-linked-lists/song-playlist.cpp
#include<iostream>
using namespace std;
class Song{
public:
string name;
string title;
Song* prev;
Song* next;
Song(){
name="";
title="";
prev=NULL;
next=NULL;
}
};
class playlist{
Song* head;
Song* current;
int count=0;
public:
playlist(){
head=NULL;
current=NULL;
}
void addsong(){
Song* newsong=new Song();
cout<<"Enter Song Name:";
cin>>newsong->name;
cout<<"Enter Song Title:";
cin>>newsong->title;
if(head==NULL){
head=newsong;
newsong->next=NULL;
newsong->prev=NULL;
current=newsong;
count++;
return;
}else{
Song* temp=head;
while(temp->next){
temp=temp->next;
}
newsong->prev=temp;
temp->next=newsong;
}
current=newsong;
count++;
}
void playcurrentsong(){
if(count<1){
cout<<"\n No Song is currently in the list.\n";
return;
}
cout<<"\nPlaying Song...........\n";
cout<<"Name: "<<current->name<<endl;
cout<<"Title: "<<current->title<<endl;
}
void nextsong(){
if(current->next==NULL){
cout<<"\nThere is no Next Song\n";
return;
}
cout<<"\nMoving to the next Song.\n";
current=current->next;
}
void prevsong(){
if(current->prev==NULL){
cout<<"\nThere is no Previous Song\n";
return;
}
cout<<"\nMoving to the previous Song.\n";
current=current->prev;
}
};
int main(){
playlist youtube;
int n;
menu:
cout<<"\n----Menu----\n";
cout<<"\n1. Add a Song";
cout<<"\n2. Play Current Song";
cout<<"\n3. Previous Song";
cout<<"\n4. Next Song";
cout<<"\n5. Exit App";
cout<<"\nEnter your choice:";
cin>>n;
switch(n){
case 1:{
youtube.addsong();
goto menu;
}
case 2:{
youtube.playcurrentsong();
goto menu;
}
case 3:{
youtube.prevsong();
goto menu;
}
case 4:{
youtube.nextsong();
goto menu;
}
case 5:{
cout<<"\nThe Application is Closing..............\n";
break;
}
default:{
cout<<"\n Invalid Enter! Chose form the menu.\n";
goto menu;
}
}
}
04-queues-and-priority-queues/README.md
# Queues and priority queues
- [simple-queue.cpp](simple-queue.cpp) adds people at the end of a linked list and serves them from the front.
- [age-priority-queue.cpp](age-priority-queue.cpp) keeps the oldest person first and serves from the front.
04-queues-and-priority-queues/age-priority-queue.cpp
#include<iostream>
using namespace std;
struct Queue {
string name;
int age;
char gender;
};
struct Node {
Queue data;
Node* next;
};
class linkedlist {
private:
Node* head;
public:
linkedlist() {
head = NULL;
}
void insertQueue() {
Node* point = new Node();
cout << "\nEnter Name: ";
cin >> point->data.name;
cout << "\nEnter Age: ";
cin >> point->data.age;
cout << "\nEnter Gender (M/F): ";
cin >> point->data.gender;
point->next = NULL;
if (head == NULL || point->data.age > head->data.age) {
point->next = head;
head = point;
} else {
Node* temp = head;
while (temp->next != NULL && temp->next->data.age >= point->data.age) {
temp = temp->next;
}
point->next = temp->next;
temp->next = point;
}
}
void serveQueue() {
if (head == NULL) {
cout << "\nThe Queue is Empty!\n";
return;
}
cout << "Processing...... \n" << head->data.name << " has been served\n";
switch (head->data.gender) {
case 'M': case 'm':
cout << "Because he is " << head->data.age << " years old\n";
break;
case 'F': case 'f':
cout << "Because she is " << head->data.age << " years old\n";
break;
default:
cout << "Because (he/she) is " << head->data.age << " years old\n";
break;
}
Node* temp = head;
head = head->next;
delete temp;
}
void displayQueue() {
if (head == NULL) {
cout << "\nThe Queue is Empty!\n";
return;
}
Node* temp = head;
int i = 1;
while (temp) {
cout << "\nPerson " << i << ":\n";
cout << "Name: " << temp->data.name << "\n";
cout << "Age: " << temp->data.age << "\n";
cout << "Gender: " << temp->data.gender << "\n";
temp = temp->next;
i++;
}
}
};
int main() {
linkedlist hospital;
int n;
menu:
cout << "\n1. Enter a person in the Queue.";
cout << "\n2. Serve a person.";
cout << "\n3. Show the list.";
cout << "\n4. Exit\n";
cout << "Enter choice: ";
cin >> n;
switch (n) {
case 1:
hospital.insertQueue();
goto menu;
case 2:
hospital.serveQueue();
goto menu;
case 3:
hospital.displayQueue();
goto menu;
case 4:
return 0;
default:
cout << "\nInvalid choice! Try again.\n";
goto menu;
}
}
04-queues-and-priority-queues/simple-queue.cpp
#include<iostream>
using namespace std;
struct Queue {
string name;
int age;
char gender;
};
struct Node {
Queue data;
Node* next;
};
class linkedlist {
private:
Node* head;
int front = -1;
int rare = -1;
public:
linkedlist() {
head = NULL;
}
void insertQueue() {
rare++;
Node* point = new Node();
cout << "\nEnter Name:";
cin >> point->data.name;
cout << "\nEnter Age:";
cin >> point->data.age;
cout << "\nEnter Gender (M/F):";
cin >> point->data.gender;
point->next = NULL;
if (rare == 0) {
front = 0;
}
if (head == NULL) {
head = point;
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = point;
}
}
void serveQueue() {
if (front >= 0) {
if (head == NULL) {
cout << "\nThe Queue is Empty!\n";
return;
}
cout << "Processing...... " << head->data.name << " has been served\n";
switch (head->data.gender) {
case 'M': case 'm':
cout << "Because he is " << head->data.age << " years old\n";
break;
case 'F': case 'f':
cout << "Because she is " << head->data.age << " years old\n";
break;
default:
cout << "Because (he/she) is " << head->data.age << " years old\n";
break;
}
Node* temp = head;
head = head->next;
delete temp;
rare--;
if (rare < 0) front = -1;
} else {
cout << "\nThe Queue is Empty!\n";
}
}
void displayQueue() {
if (front >= 0 && head != NULL) {
Node* temp = head;
int i = 1;
while (temp) {
cout << "\nPerson " << i << ":\n";
cout << "Name: " << temp->data.name << "\n";
cout << "Age: " << temp->data.age << "\n";
cout << "Gender: " << temp->data.gender << "\n";
temp = temp->next;
i++;
}
} else {
cout << "\nThe Queue is Empty!\n";
}
}
};
int main() {
linkedlist hospital;
int n;
menu:
cout << "\n1. Enter a person in the Queue.";
cout << "\n2. Serve a person.";
cout << "\n3. Show the list.";
cout << "\n4. Exit\n";
cout << "Enter choice: ";
cin >> n;
switch (n) {
case 1:
hospital.insertQueue();
goto menu;
case 2:
hospital.serveQueue();
goto menu;
case 3:
hospital.displayQueue();
goto menu;
case 4:
return 0;
default:
cout << "\nInvalid choice! Try again.\n";
goto menu;
}
}
05-graphs-and-matrices/README.md
# Graphs and matrices
- [undirected-graph-adjacency-matrix.cpp](undirected-graph-adjacency-matrix.cpp) marks connections between three vertices in an adjacency matrix and prints it.
05-graphs-and-matrices/undirected-graph-adjacency-matrix.cpp
#include<iostream>
using namespace std;
#define v 3
void add(int mat[v][v], int i, int j){
mat[i][j] = 1;
mat[j][i] = 1;
}
void display(int mat[v][v]){
for(int i = 0; i < v; i++){
for(int j = 0; j < v; j++){
cout << mat[i][j] << " ";
}
cout << endl;
}
}
int main(){
int mat[v][v] = {{0}};
add(mat, 0, 2);
add(mat, 0, 1);
add(mat, 1, 2);
display(mat);
}
06-hash-tables/README.md
# Hash tables
- [linear-probing-hash-table.cpp](linear-probing-hash-table.cpp) stores values in a fixed-size table and checks later slots when a collision occurs.
06-hash-tables/linear-probing-hash-table.cpp
#include <iostream>
using namespace std;
const int SIZE = 10;
class HashTable {
private:
int table[SIZE];
public:
HashTable() {
for (int i = 0; i < SIZE; i++)
table[i] = -1; // -1 indicates empty slot
}
// Hash function
int hashFunction(int key) {
return key % SIZE;
}
// Insert using linear probing
void insert(int key) {
int index = hashFunction(key);
// Linear probing
int startIndex = index;
while (table[index] != -1) {
index = (index + 1) % SIZE;
if (index == startIndex) {
cout << "Hash table is full!\n";
return;
}
}
table[index] = key;
}
// Search for a key
bool search(int key) {
int index = hashFunction(key);
int startIndex = index;
while (table[index] != -1) {
if (table[index] == key)
return true;
index = (index + 1) % SIZE;
if (index == startIndex)
break;
}
return false;
}
// Display the table
void display() {
cout << "Hash Table:\n";
for (int i = 0; i < SIZE; i++) {
cout << i << " --> ";
if (table[i] != -1)
cout << table[i];
else
cout << "EMPTY";
cout << endl;
}
}
};
int main() {
HashTable ht;
int n, value;
cout << "Enter number of elements to insert: ";
cin >> n;
cout << "Enter " << n << " values:\n";
for (int i = 0; i < n; i++) {
cin >> value;
ht.insert(value);
}
ht.display();
cout << "\nEnter value to search: ";
cin >> value;
if (ht.search(value))
cout << value << " found in hash table.\n";
else
cout << value << " not found in hash table.\n";
return 0;
}
07-heaps/README.md
# Heaps
- [min-heap.cpp](min-heap.cpp) stores a min-heap in an array, inserts values, and removes the minimum. The source uses an array rather than linked tree nodes.
07-heaps/min-heap.cpp
#include <iostream>
using namespace std;
#define MAX 100
class MinHeap {
int arr[MAX];
int size;
public:
MinHeap() {
size = 0;
}
// Insert an element
void insert(int val) {
if (size >= MAX) {
cout << "Heap is full!\n";
return;
}
// Add to the end
arr[size] = val;
int i = size;
size++;
// Fix the min-heap property by moving up
while (i != 0 && arr[(i - 1) / 2] > arr[i]) {
swap(arr[i], arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
}
// Display the heap as array
void display() {
cout << "Heap array:\n";
for (int i = 0; i < size; i++)
cout << arr[i] << " ";
cout << endl;
}
// Remove and return minimum (root)
int removeMin() {
if (size <= 0)
return -1;
if (size == 1) {
size--;
return arr[0];
}
int root = arr[0];
arr[0] = arr[size - 1];
size--;
heapify(0);
return root;
}
private:
// Heapify (min-heap) from given index
void heapify(int i) {
int smallest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < size && arr[left] < arr[smallest])
smallest = left;
if (right < size && arr[right] < arr[smallest])
smallest = right;
if (smallest != i) {
swap(arr[i], arr[smallest]);
heapify(smallest);
}
}
};
int main() {
MinHeap heap;
int n, val;
cout << "Enter number of elements to insert: ";
cin >> n;
cout << "Enter values:\n";
for (int i = 0; i < n; i++) {
cin >> val;
heap.insert(val);
}
heap.display();
cout << "\nMinimum value removed: " << heap.removeMin() << endl;
cout << "\nHeap after removal:\n";
heap.display();
return 0;
}
README.md
# Data Structures and Algorithms
**Course:** CSCP2033 + CSCP2031 (Lab)
The programs in this repository are grouped by topic. The source code was kept as it was; the folders and filenames are there to make it easier to find each example.
## Folders
- [01 — Binary search trees](01-binary-search-trees/README.md)
- [02 — AVL trees](02-avl-trees/README.md)
- [03 — Linked lists](03-linked-lists/README.md)
- [04 — Queues and priority queues](04-queues-and-priority-queues/README.md)
- [05 — Graphs and matrices](05-graphs-and-matrices/README.md)
- [06 — Hash tables](06-hash-tables/README.md)
- [07 — Heaps](07-heaps/README.md)
## Run a program
For a C++ example, compile one file from the repository root. Quote the path if it contains spaces:
```bash
g++ -std=c++17 "01-binary-search-trees/inorder-traversal.cpp" -o /tmp/tree-example
/tmp/tree-example
```
Run the Python linked-list example with `python3 03-linked-lists/singly-linked-list.py`.
## HTML preview
Open `index.html` to browse the files. Run `python3 generate_html.py` from the repository root to refresh both `index.html` and `generated_index.html`.