Q8.

Write a program to to convert a binary tree into doubly linked list.

#include <iostream>
#include <stack>
using namespace std;
// Definition for a binary tree node
struct TreeNode
{
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
// Convert binary tree to DLL iteratively
TreeNode *binary_tree_to_dll(TreeNode *root)
{
if (!root)
return nullptr;
TreeNode *head = nullptr; // Head of the DLL
TreeNode *prev = nullptr; // Previous node in the DLL
std::stack<TreeNode *> s;
TreeNode *curr = root;
while (curr || !s.empty())
{
while (curr)
{
s.push(curr);
curr = curr->left;
}
curr = s.top();
s.pop();
// Connect current node to the DLL
if (!head)
{
head = curr;
}
else
{
prev->right = curr;
curr->left = prev;
}
prev = curr;
curr = curr->right;
}
return head;
}
int main()
{
// Create a sample binary tree
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// Convert to DLL
TreeNode *dll_head = binary_tree_to_dll(root);
cout << "Nodes of generated doubly linked list are :" << endl;
while (dll_head)
{
cout << dll_head->data << " ";
dll_head = dll_head->right;
}
return 0;
} root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// Convert to DLL
TreeNode *dll_head = binary_tree_to_dll(root);
cout << "Nodes of generated doubly linked list are :" << endl;
while (dll_head)
{
cout << dll_head->data << " ";
dll_head = dll_head->right;
}
return 0;
}

OUTPUT:

Q9. WAP to check whether a given binary tree is balanced or not .

#include <iostream>

#include <stack>

Using namespace std;

Class Node
{

Public:

Node *lchild;

Int data;

Node *rchild;

};

Class BST

Private:

Node *root;

Public:

BST() { root = nullptr; }

Node *getRoot() { return root; }

Void iInsert(int key);

Void Inorder(Node *p);

Node *iSearch(int key);

Node *rInsert(Node *p, int key);

Node *rSearch(Node *p, int key);

Node *Delete(Node *p, int key);

Int Height(Node *p);

Node *InPre(Node *p);

Node *InSucc(Node *p);

Void createFromPreorder(int pre[], int n);

Bool isBalanced(Node *p);

};

Void BST::iInsert(int key)

Node *t = root;

Node *p;

Node *r;
// root is empty

If (root == nullptr)

P = new Node;

p->data = key;

p->lchild = nullptr;

p->rchild = nullptr;

root = p;

return;

While (t != nullptr)

R = t;

If (key < t->data)

T = t->lchild;

Else if (key > t->data)

T = t->rchild;

Else

Return;

P = new Node;

p->data = key;

p->lchild = nullptr;

p->rchild = nullptr;
 if (key < r->data)

r->lchild = p;

Else

r->rchild = p;

Void BST::Inorder(Node *p)

If (p)

Inorder(p->lchild);

Cout << p->data << “, “ << flush;

Inorder(p->rchild);

Node *BST::iSearch(int key)

Node *t = root;

While (t != nullptr)

If (key == t->data)

Return t;

Else if (key < t->data)

 {

T = t->lchild;

Else

T = t->rchild;

Return nullptr;

Node *BST::rInsert(Node *p, int key)

Node *t;

If (p == nullptr)

T = new Node;

t->data = key;

t->lchild = nullptr;

t->rchild = nullptr;

return t;

If (key < p->data)

p->lchild = rInsert(p->lchild, key);

Else if (key > p->data)

p->rchild = rInsert(p->rchild, key);

}
 Return p; // key == p->data?

Node *BST::rSearch(Node *p, int key)

If (p == nullptr)

Return nullptr;

If (key == p->data)

Return p;

Else if (key < p->data)

Return rSearch(p->lchild, key);

Else

Return rSearch(p->rchild, key);

Node *BST::Delete(Node *p, int key)

Node *q;

If (p == nullptr)

Return nullptr;
}

If (p->lchild == nullptr && p->rchild == nullptr)

If (p == root)

Root = nullptr;

Delete p;

Return nullptr;

If (key < p->data)

p->lchild = Delete(p->lchild, key);

Else if (key > p->data)

p->rchild = Delete(p->rchild, key);

Else

If (Height(p->lchild) > Height(p->rchild))

Q = InPre(p->lchild);

p->data = q->data;

p->lchild = Delete(p->lchild, q->data);

Else

Q = InSucc(p->rchild);
 p->data = q->data;

p->rchild = Delete(p->rchild, q->data);

Return p;

Int BST::Height(Node *p)

Int x;

Int y;

If (p == nullptr)

Return 0;

X = Height(p->lchild);

Y = Height(p->rchild);

Return x > y ? x + 1 : y + 1;

Node *BST::InPre(Node *p)

While (p && p->rchild != nullptr)

P = p->rchild;

Return p;

Node *BST::InSucc(Node *p)

{
 While (p && p->lchild != nullptr)

P = p->lchild;

Return p;

Void BST::createFromPreorder(int *pre, int n)

{ // Create root node

Int i = 0;

Root = new Node;

Root->data = pre[i++];

Root->lchild = nullptr;

Root->rchild = nullptr;

// Iterative steps

Node *t;

Node *p = root;

Stack<Node *> stk;

While (i < n)

// Left child case

If (pre[i] < p->data)

T = new Node;

t->data = pre[i++];

t->lchild = nullptr;

t->rchild = nullptr;

p->lchild = t;

stk.push(p);

p = t;

} Else
 { If (pre[i] > p->data && pre[i] < stk.empty() ? 32767 : stk.top()->data)

T = new Node;

t->data = pre[i++];

t->lchild = nullptr;

t->rchild = nullptr;

p->rchild = t;

p = t;

Else

P = stk.top();

Stk.pop();

Bool BST::isBalanced(Node *p)

If (p == nullptr)

Return true;

Int lh = Height(p->lchild);

Int rh = Height(p->rchild);

If (abs(lh – rh) > 1)

Return false;

Return isBalanced(p->lchild) && isBalanced(p->rchild);

}
Int main()

{ BST bst;

Bst.iInsert(10);

Bst.iInsert(5);

Bst.iInsert(20);

Bst.iInsert(8);

Bst.iInsert(30);

Bst.Inorder(bst.getRoot());

Cout << endl;

Node *temp = bst.iSearch(2);

If (temp != nullptr)

Cout << temp->data << endl;

Else

Cout << “Element not found” << endl;

// Recursive search

Temp = bst.rSearch(bst.getRoot(), 20);

If (temp != nullptr)

Cout << temp->data << endl;

Else

Cout << “Element not found” << endl;

// Recursive insert
 Bst.rInsert(bst.getRoot(), 50);

Bst.rInsert(bst.getRoot(), 70);

Bst.rInsert(bst.getRoot(), 1);

Bst.Inorder(bst.getRoot());

Cout << “\n”

<< endl;

// Inorder predecessor and inorder successor

BST bs;

Bs.iInsert(5);

Bs.iInsert(2);

Bs.iInsert(8);

Bs.iInsert(7);

Bs.iInsert(9);

Bs.iInsert(1);

Temp = bs.InPre(bs.getRoot());

Cout << “InPre: “ << temp->data << endl;

Temp = bs.InSucc(bs.getRoot());

Cout << “InSucc: “ << temp->data << endl;

Bs.Inorder(bs.getRoot());

Cout << endl;

// Delete

Bs.Delete(bs.getRoot(), 5);

Bs.Inorder(bs.getRoot());

Cout << endl;

Cout << “BST from Preorder: “ << flush;

Int pre[] = {50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24};

Int n = sizeof(pre) / sizeof(pre[0]);

BST b;
b.createFromPreorder(pre, n);

b.Inorder(b.getRoot());

cout << endl;

cout << “Is BST balanced: “ << b.isBalanced(b.getRoot()) << endl;

return 0;

OUTPUT

Q10. Write a program to traverse a directed graph using DFS.

#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[100];
void dfs(int sv, vector<int> &vis)
{
cout << sv << " ";
vis[sv] = true;
// visiting neighbors of sv
for (int i = 0; i < adj[sv].size(); i++)
{
int neighbor = adj[sv][i];
if (vis[neighbor] == false)
dfs(neighbor, vis);
 }
}
int main()
{
int n, e;
cin >> n >> e;
while (e--)
{
int f, s;
cin >> f >> s;
adj[f].push_back(s);
}
vector<int> vis(n, 0);
dfs(0, vis);
return 0;
}
OUTPUT

Q11. Write a program for quick sort.

#include <iostream>
using namespace std;
int partition(int arr[], int start, int end) {
 int pivot = arr[start];
int count = 0;
for (int i = start + 1; i <= end; i++) {
if (arr[i] <= pivot)
count++;
}
int pivotIndex = start + count;
swap(arr[pivotIndex], arr[start]);
int i = start, j = end;
while (i < pivotIndex && j > pivotIndex) {
while (arr[i] <= pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i < pivotIndex && j > pivotIndex) {
swap(arr[i++], arr[j--]);
}
}
return pivotIndex;
}
void quickSort(int arr[], int start, int end) {
if (start >= end)
return;
int p = partition(arr, start, end);
quickSort(arr, start, p - 1);
quickSort(arr, p + 1, end);
}
int main() {
int arr[] = {9, 3, 4, 2, 1, 8};
int n = 6;
quickSort(arr, 0, n - 1);
cout << "Sorted Array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}

OUTPUT: