#include <iostream>
#include <string>
using namespace std;
// Node structure
struct Node {
int value;
string color;
Node* left;
Node* right;
Node(int v, string c) : value(v), color(c), left(nullptr), right(nullptr) {}
};
// Function to insert a node into the tree
Node* insert(Node* root, int value, string color) {
if (root == nullptr) {
return new Node(value, color);
}
if (value < root->value) {
root->left = insert(root->left, value, color);
} else {
root->right = insert(root->right, value, color);
}
return root;
}
// Function to traverse and print tree in preorder
void preorder(Node* root) {
if (root == nullptr) return;
cout << root->value << " ";
preorder(root->left);
preorder(root->right);
}
// Function to traverse and print tree in inorder
void inorder(Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
// Function to traverse and print tree in postorder
void postorder(Node* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
cout << root->value << " ";
}
//Function to remove nodes with a specific color
Node* removeColor(Node* root, string colorToRemove) {
if (root == nullptr) return nullptr;
root->left = removeColor(root->left, colorToRemove);
root->right = removeColor(root->right, colorToRemove);
if (root->color == colorToRemove) {
// cout << "Removing node with value " << root->value << " and color " << root->color << endl;
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;
} else {
Node* temp = root->right;
while (temp->left != nullptr) {
temp = temp->left;
}
root->value = temp->value;
root->color = temp->color;
root->right = removeColor(root->right, colorToRemove);
}
}
return root;
}
int main() {
Node* root = nullptr;
int value;
string color;
// Input nodes
while (true) {
cin >> value;
cin >> color;
if (value == -1 && color == "null") break;
root = insert(root, value, color);
}
// Input color to remove
cin >> color;
// Remove nodes with the specified color
root = removeColor(root, color);
// Print the result
cout << "Preorder : ";
preorder(root);
cout << endl << "Inorder : ";
inorder(root);
cout << endl << "Postorder : ";
postorder(root);
cout << endl;
return 0;
}