DATA STRUCTURES AND ALGORITHMS
ASSIGNMENT 4
SALINI C P
M240869EC
EDT
1. Coding All students should have different trees Trees should have d=3 at least .
a) Take a binary tree and do tree traversals
b) coding
a) Inorder traversal: 1,15,2,20,3,10,4,23,5,5,6,25,7,12,8
Preorder traversal: 23,20,15,1,2,10,3,4,25,5,5,6,12,7,8
Postorder traversal: 1,2,15,3,4,10,20,5,6,5,7,8,12,25,23
b)
CODE
#include <iostream>
using namespace std;
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
void inorderTraversal(Node* root) {
if (root == nullptr) return;
inorderTraversal(root->left);
cout << root->data << " ";
inorderTraversal(root->right);
}
void preorderTraversal(Node* root) {
if (root == nullptr) return;
cout << root->data << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void postorderTraversal(Node* root) {
if (root == nullptr) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->data << " ";
}
int main() {
Node* root = new Node(23);
root->left = new Node(20);
root->right = new Node(25);
root->left->left = new Node(15);
root->left->right = new Node(10);
root->right->left = new Node(5);
root->right->right = new Node(12);
root->left->left->left = new Node(1);
root->left->left->right = new Node(2);
root->left->right->left = new Node(3);
root->left->right->right = new Node(4);
root->right->left->left = new Node(5);
root->right->left->right = new Node(6);
root->right->right->left = new Node(7);
root->right->right->right = new Node(8);
cout << "In-order Traversal: ";
inorderTraversal(root);
cout << endl;
cout << "Pre-order Traversal: ";
preorderTraversal(root);
cout << endl;
cout << "Post-order Traversal: ";
postorderTraversal(root);
cout << endl;
return 0;
}
OUTPUT
2. Construct a BST and do the following on it :
I) Insert
II) Delete
III) Search
IV) Max
V) Min
VI) Predecessor
VII) Successor
CODE
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
Node(int value) {
data = value;
left = nullptr;
right = nullptr;
}
};
// Insert a node
Node* insert(Node* root, int value) {
if (root == nullptr) return new Node(value);
if (value < root->data)
root->left = insert(root->left, value);
else
root->right = insert(root->right, value);
return root;
}
// Search a node
Node* search(Node* root, int value) {
if (root == nullptr || root->data == value)
return root;
if (value < root->data)
return search(root->left, value);
else
return search(root->right, value);
}
// Find the minimum value in a BST
Node* findMin(Node* root) {
while (root->left != nullptr)
root = root->left;
return root;
}
// Find the maximum value in a BST
Node* findMax(Node* root) {
while (root->right != nullptr)
root = root->right;
return root;
}
// Delete a node
Node* deleteNode(Node* root, int value) {
if (root == nullptr) return root;
if (value < root->data)
root->left = deleteNode(root->left, value);
else if (value > root->data)
root->right = deleteNode(root->right, value);
else {
// Node with one child or no child
if (root->left == nullptr) {
Node* temp = root->right;
delete root;
return temp;
} else if (root->right == nullptr) {
Node* temp = root->left;
delete root;
return temp;
}
// Node with two children
Node* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
return root;
}
// Find the predecessor
Node* findPredecessor(Node* root, int value) {
Node* current = search(root, value);
if (current == nullptr) return nullptr;
// Case 1: Node has a left subtree
if (current->left != nullptr)
return findMax(current->left);
// Case 2: No left subtree
Node* predecessor = nullptr;
Node* ancestor = root;
while (ancestor != current) {
if (value > ancestor->data) {
predecessor = ancestor;
ancestor = ancestor->right;
} else {
ancestor = ancestor->left;
}
}
return predecessor;
}
// Find the successor
Node* findSuccessor(Node* root, int value) {
Node* current = search(root, value);
if (current == nullptr) return nullptr;
// Case 1: Node has a right subtree
if (current->right != nullptr)
return findMin(current->right);
// Case 2: No right subtree
Node* successor = nullptr;
Node* ancestor = root;
while (ancestor != current) {
if (value < ancestor->data) {
successor = ancestor;
ancestor = ancestor->left;
} else {
ancestor = ancestor->right;
}
}
return successor;
}
// In-order traversal
void inOrder(Node* root) {
if (root != nullptr) {
inOrder(root->left);
cout << root->data << " ";
inOrder(root->right);
}
}
int main() {
Node* root = nullptr;
// Insert nodes
root = insert(root, 25);
root = insert(root, 20);
root = insert(root, 36);
root = insert(root, 10);
root = insert(root, 22);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 5);
root = insert(root, 12);
root = insert(root, 28);
root = insert(root, 38);
root = insert(root, 48);
cout << "In-order traversal: ";
inOrder(root);
cout << endl;
// Search
int value = 22;
Node* found = search(root, value);
if (found)
cout << "Found " << value << endl;
else
cout << value << " not found" << endl;
// Delete
root = deleteNode(root, 36);
cout << "In-order after deletion: ";
inOrder(root);
cout << endl;
// Find Min and Max
cout << "Minimum value: " << findMin(root)->data << endl;
cout << "Maximum value: " << findMax(root)->data << endl;
// Find Predecessor and Successor
Node* predecessor = findPredecessor(root, 22);
if (predecessor)
cout << "Predecessor of 22: " << predecessor->data <<
endl;
else
cout << "No predecessor found for 22" << endl;
Node* successor = findSuccessor(root, 22);
if (successor)
cout << "Successor of 22: " << successor->data << endl;
else
cout << "No successor found for 22" << endl;
return 0;
}
OUTPUT
