#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <memory.h>
#include <iterator>
#include <cassert>
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <bitset>
#include <vector>
#include <cstdio>
#include <string>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <stack>
#include <set>
#include <map>


using namespace std;

typedef int T;

#define CMP_EQ(a, b) ((a) == (b))
#define CMP_LT(a, b) ((a) < (b))
#define CMP_GT(a, b) ((a) > (b))

typedef struct Node {
    T data;
    struct Node *left;
    struct Node *right;
    struct Node *parent;
} Node;


Node* getFreeNode(T value, Node *parent) {
    Node* tmp = (Node*) malloc(sizeof(Node));
    tmp->left = tmp->right = NULL;
    tmp->data = value;
    tmp->parent = parent;
    return tmp;
}

void insert(Node **head, int value) {
    Node *tmp = NULL;
    Node *ins = NULL;
    if (*head == NULL) {
        *head = getFreeNode(value, NULL);
        return;
    }

    tmp = *head;
    while (tmp) {
        if (CMP_GT(value, tmp->data)) {
            if (tmp->right) {
                tmp = tmp->right;
                continue;
            } else {
                tmp->right = getFreeNode(value, tmp);
                return;
            }
        } else if (CMP_LT(value, tmp->data)) {
            if (tmp->left) {
                tmp = tmp->left;
                continue;
            } else {
                tmp->left = getFreeNode(value, tmp);
                return;
            }
        } else {
            exit(2);
        }
    }
}

Node* getMinNode(Node *root) {
    while (root->left) {
        root = root->left;
    }
    return root;
}


Node* getMaxNode(Node *root) {
    while (root->right) {
        root = root->right;
    }
    return root;
}

Node *getNodeByValue(Node *root, T value) {
    while (root) {
        if (CMP_GT(root->data, value)) {
            root = root->left;
            continue;
        } else if (CMP_LT(root->data, value)) {
            root = root->right;
            continue;
        } else {
            return root;
        }
    }
    return NULL;
}

void removeNodeByPtr(Node *target) {
    if (target->left && target->right) {
        Node *localMax = getMaxNode(target->left);
        target->data = localMax->data;
        removeNodeByPtr(localMax);
        return;
    } else if (target->left) {
        if (target == target->parent->left) {
            target->parent->left = target->left;
        } else {
            target->parent->right = target->left;
        }
    } else if (target->right) {
        if (target == target->parent->right) {
            target->parent->right = target->right;
        } else {
            target->parent->left = target->right;
        }
    } else {
        if (target == target->parent->left) {
            target->parent->left = NULL;
        } else {
            target->parent->right = NULL;
        }
    }
    free(target);
}


void deleteValue(Node *root, T value) {
    Node *target = getNodeByValue(root, value);
    removeNodeByPtr(target);
}

Node *addToBST(int arr[], int start, int end)
{
    if(end < start) return NULL;
    int mid = (start + end)/2;

    Node *r = (Node*) malloc(sizeof(Node));
    r->data = arr[mid];
    r->left = addToBST(arr, start, mid-1);
    r->right = addToBST(arr, mid+1, end);
    return r;
}

Node *createMinimalBST(int arr[], int size)
{
    return addToBST(arr,0,size-1);
}

void TreeToArray(Node *node, int a[]){
    static int pos = 0;
    if(node){
        TreeToArray(node->left,a);
        a[pos++] = node->data;
        TreeToArray(node->right,a);
    }
}

void printTreeReverseOrder(struct Node *node)
{
    if(node == NULL) return;
    if(node->left == NULL && node->right == NULL) {
        cout << node->data << " ";
        return;
    }

    printTreeReverseOrder(node->right);
    cout << node->data << " ";
    printTreeReverseOrder(node->left);
}

void printTreePreOrder(struct Node *node)
{
    if(node == NULL) return;

    cout << node->data << " ";
    printTreePreOrder(node->left);
    printTreePreOrder(node->right);
}

void printTreePostOrder(struct Node *node)
{
    if(node == NULL) return;

    printTreePostOrder(node->left);
    printTreePostOrder(node->right);
    cout << node->data << " ";
}

void printTreeInOrder(struct Node *node)
{
    if(node == NULL) return;

    printTreeInOrder(node->left);
    cout << node->data << " ";
    printTreeInOrder(node->right);
}

int main ()
{
    freopen("input.txt" , "r" , stdin);
    freopen("output.txt" , "w" , stdout);
    ios_base::sync_with_stdio(false);

    int a[10];
    for(int i = 1; i <= 10; ++i) {
        a[i - 1] = i;
    }
    Node *root = createMinimalBST(a, 10);


    int b[10];
    TreeToArray(root, b);
    cout << "b = ";
    for(int i = 0; i < 10; ++i) {
        cout << b[i] << ' ';
    }

    /*insert(&root, 10);
    insert(&root, 12);
    insert(&root, 8);
    insert(&root, 9);
    insert(&root, 7);
    insert(&root, 3);
    insert(&root, 4);
    printTree(root, "root", 0);
    printf("max = %d\n", getMaxNode(root)->data);
    printf("min = %d\n", getMinNode(root)->data);
    deleteValue(root, 4);
    printf("parent of 7 is %d\n", getNodeByValue(root, 7)->parent->data);
    printTree(root, "root", 0);
    deleteValue(root, 8);
    printTree(root, "root", 0);
    printf("------------------\n");
    deleteValue(root, 10);
    printTree(root, "root", 0);*/


    return 0;
}