Program:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
struct Node {
string keyword;
string meaning;
Node* left;
Node* right;
Node(string k, string m) {
keyword = k;
meaning = m;
left = right = nullptr;
};
class Dictionary {
private:
Node* root;
Node* insert(Node* root, string keyword, string meaning) {
if (root == nullptr)
return new Node(keyword, meaning);
if (keyword < root->keyword)
root->left = insert(root->left, keyword, meaning);
else if (keyword > root->keyword)
root->right = insert(root->right, keyword, meaning);
return root;
Node* findMin(Node* root) {
while (root && root->left)
root = root->left;
return root;
Node* remove(Node* root, string keyword) {
if (root == nullptr)
return root;
if (keyword < root->keyword)
root->left = remove(root->left, keyword);
else if (keyword > root->keyword)
root->right = remove(root->right, keyword);
else {
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* temp = findMin(root->right);
root->keyword = temp->keyword;
root->meaning = temp->meaning;
root->right = remove(root->right, temp->keyword);
return root;
Node* updateMeaning(Node* root, string keyword, string newMeaning)
{
if (root == nullptr) return nullptr;
if (keyword < root->keyword)
root->left = updateMeaning(root->left, keyword, newMeaning);
else if (keyword > root->keyword)
root->right = updateMeaning(root->right, keyword, newMeaning);
else {
root->meaning = newMeaning;
return root;
return root;
}
void inorder(Node* root) {
if (root != nullptr) {
inorder(root->left);
cout << "Keyword: " << root->keyword << " => Meaning: " <<
root->meaning << endl;
inorder(root->right);
void reverseInorder(Node* root) {
if (root != nullptr) {
reverseInorder(root->right);
cout << "Keyword: " << root->keyword << " => Meaning: " <<
root->meaning << endl;
reverseInorder(root->left);
int height(Node* root) {
if (root == nullptr)
return 0;
return max(height(root->left), height(root->right)) + 1;
public:
Dictionary() {
root = nullptr;
}
void addKeyword(string keyword, string meaning) {
root = insert(root, keyword, meaning);
void deleteKeyword(string keyword) {
root = remove(root, keyword);
void updateKeywordMeaning(string keyword, string newMeaning) {
root = updateMeaning(root, keyword, newMeaning);
void displayAscending() {
cout << "Dictionary in Ascending Order:" << endl;
inorder(root);
void displayDescending() {
cout << "Dictionary in Descending Order:" << endl;
reverseInorder(root);
int maxComparisons() {
return height(root);
};
int main() {
Dictionary dict;
dict.addKeyword("Apple", "A fruit that grows on a tree.");
dict.addKeyword("Banana", "A yellow fruit.");
dict.addKeyword("Carrot", "An orange root vegetable.");
dict.addKeyword("Dog", "A domesticated carnivorous mammal.");
dict.displayAscending();
cout << endl;
dict.displayDescending();
cout << endl;
s
dict.updateKeywordMeaning("Dog", "A friendly domesticated
carnivorous mammal.");
cout << "After updating 'Dog':" << endl;
dict.displayAscending();
cout << endl;
dict.deleteKeyword("Carrot");
cout << "After deleting 'Carrot':" << endl;
dict.displayAscending();
cout << endl;
cout << "Maximum comparisons required: " << dict.maxComparisons()
<< endl;
return 0;
