Indira Gandhi Delhi Technical University for Women
(Established by Govt. of Delhi vide Act 09 of 2012)
(Formerly Indira Gandhi Institute of Technology)
Kashmere Gate, Delhi – 110006
DFS Practical File December 2025
Submitted to: Submitted By:
Dr. Shweta Jindal Drishti Jain
IT Department
01904092025
IGDTUW, Delhi MCA – 1st Sem
DFS Practical File December 2025
LAB ASSIGNMENT 1
1. Two Sum
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i,j;
int n=size(nums);
vector<int> r;
for ( i=0;i<n;i++){
for (j=i+1;j<n;j++){
if((nums[i]+nums[j])==target){
r.push_back(i);
r.push_back(j);
return r ;
return r;
}};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
9. Palindrome number
class Solution {
public:
bool isPalindrome(int x) {
int y;
int temp=0;
long c=0;
y=x;
while(x>0){
temp=x%10;
x=x/10;
if ((c*10)>INT_MAX){return false;}
c=(c*10)+temp;
if(c==y){ return true; }
else if(y<0){
return false;
else return false;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
13. Roman to Integer
class Solution {
public:
int romanToInt(string as) {
int L=50,C=100,D=500,M=1000;
int res=0;
int s=0,m=7;
int b[8]={1,5,a10,50,100,500,1000,9000};
for (char c:as) {
if (c=='L'){
s=3;
res+=L;
else if (c=='C'){
s=4;
res+=C;
else if (c=='D'){
s=5;
res+=D;
else if (c=='M'){
s=6;
res+=M;
else if(c=='X'){
s=2;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
res+=10;
else if (c=='I'){
s=0;
res+=1;
else if (c=='V'){
s=1;
res+=5;
if (b[m]<b[s]){
res-=b[m]*2;
m=s;
return res;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 2
20. Valid Parentheses
class Solution {
public:
bool isValid(string s) {
int ab = 0;
char lo[10000];
for (char c : s) {
if (c == '(' || c == '{' || c == '[') {
lo[ab] = c;
ab++;
} else {
if (ab == 0) return false;
if (c == ')') {
if (lo[ab-1] == '(') {
ab--;
} else {
return false;
}
} else if (c == ']') {
if (lo[ab-1] == '[') {
ab--;
} else {
return false;
}
} else if (c == '}') {
if (lo[ab-1] == '{') {
ab--;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
} else {
return false;
}
}
}
}
return ab == 0; // all matched
}
};
21. Merge Two Sorted Lists
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* temp1 = list1;
ListNode* temp2 = list2;
ListNode* h = new ListNode(0);
ListNode* list3 = h;
while (temp1 != NULL && temp2 != NULL) {
if (temp1->val <= temp2->val) {
list3->next = temp1;
temp1 = temp1->next;
else {
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
list3->next = temp2;
temp2 = temp2->next;
list3 = list3->next;
//if any elements are left:
if (temp1 != NULL) {
list3->next = temp1;
if (temp2 != NULL) {
list3->next = temp2;
return h->next;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 3
26. Remove Duplicates from Sorted Array
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// if array is empty
if ([Link]() == 0) return 0;
int i = 0;
for (int j = 1; j < [Link](); j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
return i + 1;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
27. Remove Element
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
if ([Link]()==0) return 0;
int i=0;
int j=0;
for (int i; i < [Link](); i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
return j;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
28. Find the Index of the First Occurrence in a
String
class Solution {
public:
int strStr(string haystack, string needle) {
int j = [Link]();
if (j == 0) return 0;
for (int i = 0; i < [Link](); i++) {
if (haystack[i] == needle[0]) {
int a = i; // haystack pointer
int b = 0; // needle pointer
int f = 0;
while (b < j && a < [Link]()) {
if (haystack[a] != needle[b]) {
f = -1;
break;
a++;
b++;
if (f == 0 && b == j) {
return i;
}}}
return -1;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 4
35. Search Insert Position
Given a sorted array of distinct integers and a target value, return the index if the
target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Code:
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l=0;
int r=[Link]()-1;
while(l<=r){
int mid=(l+r)/2;
if(nums[mid]==target){
return mid;
else if(target<nums[mid]){
r=mid-1;
else{
l=mid+1;
return l;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
58. Length of Last Word
Given a string consisting of words and spaces, return the length of the last word in
the string.
Code:
class Solution {
public:
int lengthOfLastWord(string s) {
int i = [Link]()-1;
int count=0;
while(i>=0 && s[i]==' '){
i--;
}
while(i>=0 && s[i]!=' '){
count++;
i--;
}
return count;
}
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
66. Plus One
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int i= [Link]()-1;
while (i >= 0 and digits[i] == 9){
digits[i]=0;
i--;
}
if(i>=0){
digits[i]++;
}
else{
[Link]([Link](), 1);
}
return digits;
}
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
67. Add Binary
class Solution {
public:
string addBinary(string a, string b) {
int carry=0;
string out="";
int i=[Link]()-1;
int j=[Link]()-1;
while(i>=0 || j>=0 || carry){
int sum=carry;
if (i>=0){
sum +=a[i]-'0';
i--;
}
if (j>=0) {
sum+= b[j]-'0';
j--;
}
out= char(sum%2 +'0')+out;
carry=sum/2;
}
return out;
}
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
69. Sqrt(x)
class Solution {
public:
int mySqrt(int x) {
for(int i=0;i<=x;i++){
long long sq = 1LL * i * i;
if (sq==x){
return i;
}
if (sq>x){
return i-1;
}
}
return 0;
}
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
70. Climing Staris
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
int a = 1; //ways to reach step 1
int b = 2; //ways to reach step 2
int c;
for (int i = 3; i <= n; i++) {
c = a + b; //f(n) = f(n-1) + f(n-2)
a = b;
b = c;
return b;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 5
83. Remove Duplicates from Sorted List
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* temp = hCead;
while (temp != nullptr && temp->next != nullptr) {
if (temp->val == temp->next->val) {
temp->next = temp->next->next;
} else {
temp = temp->next;
return head;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
88. Merge Sorted Array
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i=m-1;
int j=n-1;
int k=m+n-1;
while (i>=0 && j >=0){
if (nums1[i]>nums2[j]){
nums1[k]=nums1[i];
k--;i--;
else {
nums1[k]=nums2[j];
k--;j--;
while(j>=0){
nums1[k--]=nums2[j--];
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 6
540. Single Element in a Sorted Array
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left=0,right=[Link]()-1;
while (left<right) {
int mid= (left+right)/2;
if (mid%2==1) mid--; //even mid
if (nums[mid] == nums[mid+1])
left=mid+2;
else
right=mid;
return nums[left];
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
QuEuE AS STAckS
#include <iostream>
#include <stack>
using namespace std;
class Queue {
private:
stack<int> s1, s2;
public:
void enqueue(int x) {
[Link](x);
int dequeue() {
if ([Link]() && [Link]()) {
cout << "Queue is empty\n";
return -1;
if ([Link]()) {
while (![Link]()) {
[Link]([Link]());
[Link]();
int value = [Link]();
[Link]();
return value;
int front() {
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
if ([Link]() && [Link]()) {
cout << "Queue is empty\n";
return -1;
if ([Link]()) {
while (![Link]()) {
[Link]([Link]());
[Link]();
return [Link]();
bool empty() {
return [Link]() && [Link]();
};
int main() {
Queue q;
[Link](10);
[Link](20);
[Link](30);
cout << [Link]() << endl; // 10
cout << [Link]() << endl; // 10
cout << [Link]() << endl; // 20
[Link](40);
cout << [Link]() << endl; // 30
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
return 0;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 7
111. Minimum Depth of Binary Tree
to the nearest leaf node.
Code:
class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) return 0;
int left=minDepth(root->left);
int right=minDepth(root->right);
if (!root->left) return right+1;
if (!root->right) return left+1;
return min(left, right)+1;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
169. Majority Element
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate=0, count =0;
for (int n:nums){
if(count==0) candidate=n;
count+=(n==candidate? 1: -1);
return candidate;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
[Link] Sheet Column Number.
class Solution {
public:
int titleToNumber(string columnTitle) {
long long result = 0;
for (char c : columnTitle) {
int value = c - 'A' + 1;
result = result * 26 + value;
return result;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
190. Reverse Bits.
class Solution {
public:
int reverseBits(int n) {
uint32_t result = 0;
for (int i = 0; i < 32; i++) {
result <<= 1;
result |= (n & 1);
n >>= 1;
return result;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
[Link] Linked List.
Code:
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (!head || !head->next) return true;
// 1. Find middle (slow will stop at middle)
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
// 2. Reverse second half
ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr) {
ListNode* nextNode = curr->next;
curr->next = prev;
prev = curr;
curr = nextNode;
ListNode* left = head;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
ListNode* right = prev;
while (right) {
if (left->val != right->val)
return false;
left = left->next;
right = right->next;
return true;
};
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
LAB ASSIGNMENT 8
BST insertion, pre, post, inorder traversal and deletion
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
};
Node* createNode(int value) {
Node* newNode = new Node();
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
Node* insert(Node* root, int value) {
if (root == NULL) {
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
void inorder(Node* root) {
if (root != NULL) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
void preorder(Node* root) {
if (root != NULL) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
void postorder(Node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
Node* findMin(Node* root) {
while (root->left != NULL)
root = root->left;
return root;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
Node* deleteNode(Node* root, int value) {
if (root == NULL) return root;
if (value < root->data)
root->left = deleteNode(root->left, value);
else if (value > root->data)
root->right = deleteNode(root->right, value);
else {
if (root->left == NULL && root->right == NULL) {
delete root;
return NULL;
else if (root->left == NULL) {
Node* temp = root->right;
delete root;
return temp;
else if (root->right == NULL) {
Node* temp = root->left;
delete root;
return temp;
Node* temp = findMin(root->right); // inorder successor
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
return root;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
int main() {
Node* root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 70);
insert(root, 20);
insert(root, 40);
insert(root, 60);
insert(root, 80);
cout << "Inorder: ";
inorder(root);
cout << "\nPreorder: ";
preorder(root);
cout << "\nPostorder: ";
postorder(root);
cout << "\n\nDeleting 20...\n";
root = deleteNode(root, 20);
inorder(root);
cout << "\nDeleting 30...\n";
root = deleteNode(root, 30);
inorder(root);
cout << "\nDeleting 50...\n";
root = deleteNode(root, 50);
inorder(root);
return 0;
Drishti Jain 01904092025 MCA 1st year
DFS Practical File December 2025
Drishti Jain 01904092025 MCA 1st year