//Complete function: pair sort(Node* p);

//use recursion, but while loop is allowed.

//sorting such that ascending sequence in pre-order traversal

//function returns a pair of pointers, which point to the node with the smallest value and the node with the largest values in the tree rooted at node pointed by p.

#include

#include

using namespace std;

class Node {

public:

int value;

Node* l_child;

Node* r_child;

Node() : l_child(nullptr), r_child(nullptr) {}

Node(int i) :value(i), l_child(nullptr), r_child(nullptr) {}

};

class Tree {

public:

Node* root;

Tree() : root(nullptr) {}

Node* makeTree(int n, int m);

void printTree1(Node* p);

void printTree2(Node* p); //pre-order printing

void printTree3(Node* p);

void mirror(Node* p);

int sum(Node* p);

Node* mirrorCopy(Node* p);

void minHeap(Node* p);

pair sort(Node* p);

Node* Tree::mirrorCopy(Node* p) {

if (!p) return nullptr;

if (!p->l_child) return p;

Node* p1, * p2;

p1 = mirrorCopy(p->l_child);

p2 = mirrorCopy(p->r_child);

if (p1->value > p2->value) {

swap(p->l_child, p->r_child);

swap(p1, p2);

}

if (p->value > p2->value) swap(p->value, p2->value);

if ((p->l_child->value < p->value) || (p->r_child->value < p->value)) {

if (p->l_child->value <= p->r_child->value) {

int i = p->value;

p->value = p->l_child->value;

p->l_child->value = i;

mirrorCopy(p->l_child);

}

else {

int i = p->value;

p->value = p->r_child->value;

p->r_child->value = i;

mirrorCopy(p->r_child);

}

}

return p2;

}

void Tree::minHeap(Node* p) {

if (!p || !p->l_child || !p->r_child) return;

minHeap(p->l_child);

minHeap(p->r_child);

if ((p->l_child->value < p->value) || (p->r_child->value < p->value)) {

if (p->l_child->value <= p->r_child->value) {

int i = p->value;

p->value = p->l_child->value;

p->l_child->value = i;

minHeap(p->l_child);

}

else {

int i = p->value;

p->value = p->r_child->value;

p->r_child->value = i;

minHeap(p->r_child);

}

}

if (p->l_child->value < p->r_child->value) swap(p->l_child, p->r_child);

}

pairTree::sort(Node* p) {

// write code below

//use recursion, but while loop is allowed.

//sorting such that ascending sequence in pre-order traversal

//function returns a pair of pointers, which point to the node with the smallest value and the node with the largest values in the tree rooted at node pointed by p.

}

int Tree::sum(Node* p) {

if (!p) return 0;

if (!p->l_child) return p->value;

return p->value + sum(p->l_child) + sum(p->r_child);

}

void Tree::mirror(Node* p) {

if (!p || !p->l_child) return;

mirror(p->l_child);

mirror(p->r_child);

swap(p->l_child, p->r_child);

}

Node* Tree::makeTree(int n, int m) {

Node* p = new Node(rand() % m);

if (n == 1) return p;

p->l_child = makeTree(n - 1, m);

p->r_child = makeTree(n - 1, m);

return p;

}

void Tree::printTree1(Node* p) { //in-order printing

if (p == nullptr) return;

printTree1(p->l_child);

cout << p->value << " ";

printTree1(p->r_child);

}

void Tree::printTree2(Node* p) {

if (p == nullptr) return;

cout << p->value << " ";

printTree2(p->l_child);

printTree2(p->r_child);

}

void Tree::printTree3(Node* p) {

if (p == nullptr) return;

printTree3(p->l_child);

printTree3(p->r_child);

cout << p->value << " ";

}

int main() {

Tree T1;

T1.root = T1.makeTree(4, 20);

T1.printTree1(T1.root);

cout << endl;

T1.printTree2(T1.root);

cout << endl;

T1.printTree3(T1.root);

cout << endl;

Tree T2;

T2.root = T1.mirrorCopy(T1.root);

T2.printTree1(T2.root);

cout << endl;

T2.printTree2(T2.root);

cout << endl;

T2.printTree3(T2.root);

cout << endl;

T2.minHeap(T2.root);

T2.printTree1(T2.root);

cout << endl;

T2.printTree2(T2.root);

cout << endl;

T2.printTree3(T2.root);

cout << endl;

Tree T3;

T3.root = T3.makeTree(5, 20);

T3.sort(T3.root);

T3.printTree1(T3.root);

cout << endl;

T3.printTree2(T3.root);

cout << endl;

T3.printTree3(T3.root);

cout << endl;

return 0;

}