#include<bits/stdc++.
h>
using namespace std;
template <typename T>
class Node {
public:
T data;
Node<T>* left, *right;
Node(T d) {
data = d;
left = nullptr;
right = nullptr;
}
Node(T d, Node<T>* l, Node<T>* r) {
data = d;
left = l;
right = r;
}
};
template <typename T>
class Tree {
private:
Node<T>* root;
Node<T>* insert(Node<T>* node, T value) {
if (!node) return new Node<T>(value);
if (value < node->data)
node->left = insert(node->left, value);
else
node->right = insert(node->right, value);
return node;
}
Node<T>* search(Node<T>* node, T key) {
if (!node || node->data == key) return node;
if (key < node->data) return search(node->left, key);
else return search(node->right, key);
}
Node<T>* findMin(Node<T>* node) {
while (node && node->left)
node = node->left;
return node;
}
Node<T>* deleteNode(Node<T>* node, T key) {
if (!node) return node;
if (key < node->data)
node->left = deleteNode(node->left, key);
else if (key > node->data)
node->right = deleteNode(node->right, key);
else {
if (!node->left) {
Node<T>* temp = node->right;
delete node;
return temp;
}
else if (!node->right) {
Node<T>* temp = node->left;
delete node;
return temp;
}
Node<T>* temp = findMin(node->right);
node->data = temp->data;
node->right = deleteNode(node->right, temp->data);
}
return node;
}
public:
Tree() : root(nullptr) {}
void insert(T value) {
root = insert(root, value);
}
void search(T key) {
Node<T>* result = search(root, key);
if (result)
cout << "Found: " << result->data << endl;
else
cout << "Not Found" << endl;
}
void deleteValue(T key) {
root = deleteNode(root, key);
}
Node<T>* getRoot() const {
return root;
}
void recinorder(Node<T>* node) {
if (!node) return;
recinorder(node->left);
cout << node->data << " ";
recinorder(node->right);
}
void recpreorder(Node<T>* node) {
if (!node) return;
cout << node->data << " ";
recpreorder(node->left);
recpreorder(node->right);
}
void recpostorder(Node<T>* node) {
if (!node) return;
recpostorder(node->left);
recpostorder(node->right);
cout << node->data << " ";
}
void itinorder() {
stack<Node<T>*> st;
Node<T>* current = root;
while (current || ![Link]()) {
while (current) {
[Link](current);
current = current->left;
}
current = [Link]();
[Link]();
cout << current->data << " ";
current = current->right;
}
}
void preiterative() {
if (!root) return;
stack<Node<T>*> st;
[Link](root);
while (![Link]()) {
Node<T>* current = [Link]();
[Link]();
cout << current->data << " ";
if (current->right) [Link](current->right);
if (current->left) [Link](current->left);
}
}
void postiterative() {
if (!root) return;
stack<Node<T>*> st1, st2;
[Link](root);
while (![Link]()) {
Node<T>* curr = [Link]();
[Link]();
[Link](curr);
if (curr->left) [Link](curr->left);
if (curr->right) [Link](curr->right);
}
while (![Link]()) {
cout << [Link]()->data << " ";
[Link]();
}
}
void postorderIterativeOneStack() {
stack<Node<T>*> st;
Node<T>* current = root;
Node<T>* lastVisited = nullptr;
while (![Link]() || current) {
if (current) {
[Link](current);
current = current->left;
} else {
Node<T>* peek = [Link]();
if (peek->right && lastVisited != peek->right) {
current = peek->right;
} else {
cout << peek->data << " ";
lastVisited = peek;
[Link]();
}
}
}
}
};