C++ Programs

Data Structures & Algorithms

01. BookStore using BST

02. Threaded Binary Tree
03. AVL Tree
04. BFS Traversal
05. DFS Traversal
06. Transportation Network (Graph)
07. Prim's MST
08. Kruskal's MST
09. Dijkstra's Shortest Path
10. Naive Pattern Matching
11. Set Operations - Language Speakers
12. Optimal Binary Search Tree (OBST)
13. Set Operations (Union, Intersection, Difference)
Program 01: BookStore using BST
File: [Link]

#include <iostream>
using namespace std;

class Book {
public:
string title, author;
Book* left;
Book* right;

Book(string t, string a) {
title = t;
author = a;
left = right = NULL;
}
};

class BookStore {
private:
Book* root;

Book* insert(Book* node, string title, string author) {

if (node == NULL)
return new Book(title, author);

if (title < node->title)

node->left = insert(node->left, title, author);
else
node->right = insert(node->right, title, author);

return node;
}

Book* searchByTitle(Book* node, string title) {

if (node == NULL || node->title == title)
return node;

if (title < node->title)

return searchByTitle(node->left, title);
else
return searchByTitle(node->right, title);
}

void searchByAuthor(Book* node, string author) {

if (node == NULL) return;

searchByAuthor(node->left, author);

if (node->author == author)
cout << "Found: " << node->title << " - " << node->author << endl;

searchByAuthor(node->right, author);
}

void inorder(Book* node) {

if (node == NULL) return;

inorder(node->left);
cout << node->title << " - " << node->author << endl;
inorder(node->right);
}

// ■ DELETE FUNCTIONS
Book* findMin(Book* node) {
while(node->left) node = node->left;
 return node;
}

Book* deleteBook(Book* node, string title) {

if(node == NULL) return NULL;

if(title < node->title)

node->left = deleteBook(node->left, title);
else if(title > node->title)
node->right = deleteBook(node->right, title);
else {
if(node->left == NULL) return node->right;
if(node->right == NULL) return node->left;

Book* temp = findMin(node->right);

node->title = temp->title;
node->author = temp->author;
node->right = deleteBook(node->right, temp->title);
}
return node;
}

public:
BookStore() {
root = NULL;
}

void addBook(string title, string author) {

root = insert(root, title, author);
cout << "Book Added Successfully!\n";
}

void findByTitle(string title) {

Book* found = searchByTitle(root, title);
if (found)
cout << "Found: " << found->title << " - " << found->author << endl;
else
cout << "Book Not Found\n";
}

void findByAuthor(string author) {

searchByAuthor(root, author);
}

void updateBook(string title, string newAuthor) {

Book* found = searchByTitle(root, title);
if (found) {
found->author = newAuthor;
cout << "Book Updated Successfully!\n";
} else {
cout << "Book Not Found\n";
}
}

void removeBook(string title) {

root = deleteBook(root, title);
cout << "Book Deleted (if existed)\n";
}

void displayBooks() {
cout << "\nBook Catalog:\n";
inorder(root);
}
};

int main() {
BookStore store;
 int choice;
string title, author;

do {
cout << "\n1. Add Book";
cout << "\n2. Search by Title";
cout << "\n3. Search by Author";
cout << "\n4. Update Book";
cout << "\n5. Display All Books";
cout << "\n6. Delete Book";
cout << "\n0. Exit";
cout << "\nEnter choice: ";
cin >> choice;
[Link]();

switch(choice) {
case 1:
cout << "Enter Title: ";
getline(cin, title);
cout << "Enter Author: ";
getline(cin, author);
[Link](title, author);
break;

case 2:
cout << "Enter Title: ";
getline(cin, title);
[Link](title);
break;

case 3:
cout << "Enter Author: ";
getline(cin, author);
[Link](author);
break;

case 4:
cout << "Enter Title to Update: ";
getline(cin, title);
cout << "Enter New Author: ";
getline(cin, author);
[Link](title, author);
break;

case 5:
[Link]();
break;

case 6:
cout << "Enter Title to Delete: ";
getline(cin, title);
[Link](title);
break;
}

} while(choice != 0);

return 0;
}
Program 02: Threaded Binary Tree
File: [Link]

#include <iostream>
using namespace std;

struct Node {
int data;
Node* left;
Node* right;
bool rthread;
};

class ThreadedBT {
Node* root;

public:
ThreadedBT() { root = NULL; }

Node* leftMost(Node* node) {

while (node && node->left)
node = node->left;
return node;
}

void insert(int key) {

Node* ptr = root;
Node* parent = NULL;

while (ptr) {
if (key == ptr->data) {
cout << "Duplicate not allowed\n";
return;
}

parent = ptr;

if (key < ptr->data) {

if (!ptr->left) break;
ptr = ptr->left;
} else {
if (ptr->rthread) break;
ptr = ptr->right;
}
}

Node* temp = new Node{key, NULL, NULL, true};

if (!parent)
root = temp;
else if (key < parent->data) {
parent->left = temp;
temp->right = parent; // inorder successor
} else {
temp->right = parent->right;
parent->right = temp;
parent->rthread = false;
}

cout << "Inserted\n";

}

void inorder() {
if (!root) {
cout << "Tree is empty\n";
return;
}
 Node* cur = leftMost(root);

while (cur) {
cout << cur->data << " ";
if (cur->rthread)
cur = cur->right;
else
cur = leftMost(cur->right);
}
cout << endl;
}

void search(int key) {

Node* ptr = root;

while (ptr) {
if (key == ptr->data) {
cout << "Found\n";
return;
}

if (key < ptr->data)

ptr = ptr->left;
else {
if (ptr->rthread)
ptr = NULL;
else
ptr = ptr->right;
}
}

cout << "Not Found\n";

}
};

int main() {
ThreadedBT t;
int choice, val;

do {
cout << "\[Link]\[Link]\[Link]\[Link]\nChoice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value: ";
cin >> val;
[Link](val);
break;

case 2:
[Link]();
break;

case 3:
cout << "Enter value to search: ";
cin >> val;
[Link](val);
break;

case 4:
cout << "Exiting...\n";
break;

default:
cout << "Invalid choice\n";
}
 } while (choice != 4);

return 0;
}
Program 03: AVL Tree
File: [Link]

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
int data, height;
Node *left, *right;
};

int height(Node* n) {
return n ? n->height : 0;
}

Node* newNode(int x) {
Node* n = new Node();
n->data = x;
n->left = n->right = NULL;
n->height = 1;
return n;
}

int getBalance(Node* n) {
return n ? height(n->left) - height(n->right) : 0;
}

Node* rightRotate(Node* y) {
Node* x = y->left;
y->left = x->right;
x->right = y;
y->height = 1 + max(height(y->left), height(y->right));
x->height = 1 + max(height(x->left), height(x->right));
return x;
}

Node* leftRotate(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
x->height = 1 + max(height(x->left), height(x->right));
y->height = 1 + max(height(y->left), height(y->right));
return y;
}

Node* insert(Node* root, int key) {

if (!root) return newNode(key);

if (key < root->data)

root->left = insert(root->left, key);
else
root->right = insert(root->right, key);

root->height = 1 + max(height(root->left), height(root->right));

int bf = getBalance(root);

if (bf > 1 && key < root->left->data) return rightRotate(root); // LL

if (bf < -1 && key > root->right->data) return leftRotate(root); // RR
if (bf > 1 && key > root->left->data) {
root->left = leftRotate(root->left); return rightRotate(root); // LR
}
if (bf < -1 && key < root->right->data) {
root->right = rightRotate(root->right); return leftRotate(root);// RL
}
return root;
}

bool search(Node* root, int key) {

if (!root) return false;
if (root->data == key) return true;
if (key < root->data) return search(root->left, key);
return search(root->right, key);
}

int main() {
Node* root = NULL;
int n, x;

cin >> n;
while (n--) {
cin >> x;
root = insert(root, x);
}

cin >> x;
cout << (search(root, x) ? "Found" : "Not Found");

return 0;
}
Program 04: BFS Traversal
File: [Link]

//bfs
#include <bits/stdc++.h>
using namespace std;

void display(int n, vector<vector<int>>& adj) {

for(int i = 1; i <= n; i++) {
cout << i << " -> ";
for(auto x : adj[i]) cout << x << ' ';
cout << endl;
}
}

vector<int> bfs(vector<vector<int>>& adj) {

int n = [Link]();
vector<int> bfs;
vector<int> vis(n, 0);
queue<int> q;
[Link](1);
vis[1] = 1;
while(![Link]()) {
int node = [Link]();
[Link]();
for(auto it : adj[node]){
if(!vis[it]){
vis[it] = 1;
[Link](it);
}
}
bfs.push_back(node);
}
return bfs;
}

int main() {
int n, m; cin >> n >> m;
vector<vector<int>> adj(n + 1); // 1 to n vertices
for(int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> ans = bfs(adj);

cout << "BFS Traversal: ";

for(auto x : ans)
cout << x << " ";
}
Program 05: DFS Traversal
File: [Link]

//DFS

#include <bits/stdc++.h>
using namespace std;

#define ent endl

typedef long long ll;
typedef long double ld;

typedef vector<int> vi;

typedef vector<ld> vd;
typedef vector<ll> vl;

#define FOR(i, a, b) for (int i=a; i<(b); i++)

#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

// Problem Statement
/*

*/

// Small Observatins
/*

*/

/*

*/

// Claims on algo
/*

*/

void solve() {

// Golden Rules
/*
Solutions are simple.

Proofs are simple.

Implementations are simple.

*/
vector<int> dfs(vector<vector<int>>& adj) {
int n = [Link]();
vector<int> dfs;
vector<int> vis(n, 0);
stack<int> st;
[Link](1);
vis[1] = 1;
while(![Link]()) {
int node = [Link]();
[Link]();
for(auto it : adj[node]){
 if(!vis[it]){
vis[it] = 1;
[Link](it);
}
}
dfs.push_back(node);
}
return dfs;
}

void display(int n, vector<vector<int>>& adj) {

for(int i = 1; i <= n; i++) {
cout << i << " -> ";
for(auto x : adj[i]) cout << x << ' ';
cout << endl;
}
}

int main() {
ios_base::sync_with_stdio(0); [Link](0);
int n, m; cin >> n >> m;
vector<vector<int>> adj(n + 1); // 1 to n vertices
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> ans;
ans = dfs(adj);
cout << "DFS Traversal: ";
for(auto x : ans)
cout << x << " ";
return 0;
}
Program 06: Transportation Network (Graph)
File: [Link]

#include<bits/stdc++.h>
using namespace std;

int main() {
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> adj(n);
// u, v, wt
for(int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}

cout << ".........................Transportation Network......................." << endl;

for(int i = 0; i < n; i++) {
cout <<"City " << i << " -> ";
for(auto it : adj[i]) {
cout << '(' << [Link] << ',' << [Link] << ") ";
}
cout << endl;
}
}
Program 07: Prim's MST
File: [Link]

// 5 5
// 0 1 2
// 0 2 6
// 1 2 3
// 1 3 8
// 2 4 5

#include <bits/stdc++.h>
using namespace std;

int main() {
int n, m; cin >> n >> m;
vector<vector<pair<int, int>>> adj(n);
for(int i = 0; i < m; i++) {
int u, v, w; cin >> u >> v >> w;
adj[v].push_back({u, w});
adj[u].push_back({v, w});
}
vector<int> vis(n, 0);
int wt = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
[Link]({0, 0});
while(![Link]()){
int w = [Link]().first;
int node = [Link]().second;
[Link]();
if(vis[node]) continue;

vis[node] = 1;
wt += w;
for(auto it : adj[node]) {
int adjNode = [Link];
int wtt = [Link];
if(!vis[adjNode]) [Link]({wtt, adjNode});
}
}
cout << "MST wt: " << wt << endl;
return 0;
}
Program 08: Kruskal's MST
File: [Link]

// User function Template for C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> parent;
int find(int x) {
if(parent[x] == x) return x;
return parent[x] = find(parent[x]);
}

void unite(int a, int b) {

a = find(a);
b = find(b);
parent[a] = b;
}
int kruskalsMST(int V, vector<vector<int>> &edges) {
// wt, u, v
vector<pair<int, pair<int, int>>> adj;
for(auto it : edges) {
adj.push_back({it[2], {it[0], it[1]}});
}
sort([Link](), [Link]());
[Link](V);
for(int i = 0; i < V; i++) parent[i] = i; // khudka parent khud hi.. (starting meinn)
int mstWt = 0;
for(auto it : adj) {
int w = [Link];
int u = [Link];
int v = [Link];

if(find(u) != find(v)) {
mstWt += w;
unite(u, v);
}
}

return mstWt;
}
};
Program 09: Dijkstra's Shortest Path
File: [Link]

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
int n, m;
cin >> n >> m; // nodes, edges

vector<vector<pair<int,int>>> adj(n);

// input edges: u v weight

// adj list have -> nodes, edgeWt
for(int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w}); // remove if directed
}

int src, dest;

cin >> src >> dest;

vector<int> dist(n, INF);

dist[src] = 0;

// stores {distance, node}

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
[Link]({0, src});

while(![Link]()) {
auto temp = [Link](); [Link]();
int dis = [Link];
int node = [Link];

for(auto it : adj[node]) {
int adjNode = [Link];
int edgeWt = [Link];

if(dis + edgeWt < dist[adjNode]) {

dist[adjNode] = dis + edgeWt;
[Link]({dist[adjNode], adjNode});
}
}
}

cout << "Shortest Distance: " << dist[dest];

return 0;
}
Program 10: Naive Pattern Matching
File: [Link]

#include<iostream>
using namespace std;

int main() {
string text, pattern; cin >> text >> pattern;
int n = [Link](), m = [Link]();

for(int i = 0; i <= n - m; i++) { // remember the last position is n - m only we cannot go beyond that and it's <= onl
int j;
for(j = 0; j < m; j++) {
if(text[i + j] != pattern[j]) break;
}
if(j == m) {
cout << "Pattern Found at index: " << i << endl;
return 0;
}
}
cout << "Pattern is not found" << endl;

}
Program 11: Set Operations - Language Speakers
File: [Link]

#include <bits/stdc++.h>
using namespace std;

int main() {
int n1, n2;
set<int> spanish, german;

cout << "Enter number of Spanish speakers: ";

cin >> n1;

cout << "Enter IDs of Spanish speakers:\n";

for(int i = 0; i < n1; i++) {
int x; cin >> x;
[Link](x);
}

cout << "Enter number of German speakers: ";

cin >> n2;

cout << "Enter IDs of German speakers:\n";

for(int i = 0; i < n2; i++) {
int x; cin >> x;
[Link](x);
}

// ■ Union (Spanish ∪ German)

set<int> uni;
for(auto x : spanish) [Link](x);
for(auto x : german) [Link](x);

// ■ Intersection (both languages)

set<int> inter;
for(auto x : spanish) {
if([Link](x)) [Link](x);
}

// ■ Difference (Spanish only)

set<int> diff;
for(auto x : spanish) {
if() [Link](x);
}

// Output
cout << "\nAll attendees (Union): ";
for(auto x : uni) cout << x << " ";

cout << "\nSpeaks both (Intersection): ";

for(auto x : inter) cout << x << " ";

cout << "\nOnly Spanish (Difference): ";

for(auto x : diff) cout << x << " ";

return 0;
}
Program 12: Optimal Binary Search Tree (OBST)
File: [Link]

#include <bits/stdc++.h>
using namespace std;

int OBST(vector<int>& f, int n) {

vector<vector<int>> dp(n, vector<int>(n));

for(int i = 0; i < n; i++)

dp[i][i] = f[i];

for(int len = 2; len <= n; len++) {

for(int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = INT_MAX;

int sum = 0;
for(int k = i; k <= j; k++) sum += f[k];

for(int r = i; r <= j; r++) {

int left = (r > i) ? dp[i][r-1] : 0;
int right = (r < j) ? dp[r+1][j] : 0;
dp[i][j] = min(dp[i][j], left + right + sum);
}
}
}
return dp[0][n-1];
}

int main() {
int n;
cin >> n;

vector<int> f(n);
for(int i = 0; i < n; i++) cin >> f[i];

cout << "Optimal Cost: " <<OBST(f, n);

}
Program 13: Set Operations (Union, Intersection, Difference)
File: [Link]

#include <bits/stdc++.h>
using namespace std;

int main() {
int n1, n2;
cin >> n1;

set<int> A, B;

for(int i = 0; i < n1; i++) {

int x; cin >> x;
[Link](x);
}

cin >> n2;

for(int i = 0; i < n2; i++) {
int x; cin >> x;
[Link](x);
}

// ■ Union ->all elts

set<int> uni;
for(auto x : A) [Link](x);
for(auto x : B) [Link](x);

// ■ Intersection-> common elements

set<int> inter;
for(auto x : A) {
if([Link](x)) [Link](x);
}

// ■ Difference (A - B) -> those who are only in A

set<int> diff;
for(auto x : A) {
if() [Link](x);
}

// Output
cout << "Union: ";
for(auto x : uni) cout << x << " ";

cout << "\nIntersection: ";

for(auto x : inter) cout << x << " ";

cout << "\nDifference (A-B): ";

for(auto x : diff) cout << x << " ";
}