#include <iostream>
#include<queue>
using namespace std;

struct Node {
    int key;
    Node* p_left;
    Node* p_right;
};


Node* creatNode(int data) {
    Node* p = new Node;

    p->key = data;
    p->p_left = NULL;
    p->p_right = NULL;
    
    return p;
}
//NLR
void printPreOder(Node* root) {    //NLR
    if (root == NULL)
        return;

    cout << root->key << " ";
    printPreOder(root->p_left);
    printPreOder(root->p_right);
}
//LNR
void printInOder(Node* root) {    //LNR
    if (root == NULL)
        return;

    printPreOder(root->p_left);
    cout << root->key << " ";   
    printPreOder(root->p_right);
}
//LRN
void printPostOder(Node* root) {    //LRN
    if (root == NULL)
        return;

    printPreOder(root->p_left);
    printPreOder(root->p_right);
    cout << root->key << " ";
}

// calculate the height of the given BST
int height(Node* root)  
{
    if (root == NULL)
        return 0;
    else
    {

        int lheight = height(root->p_left);
        int rheight = height(root->p_right);

        if (lheight > rheight)
            return(lheight + 1);
        else return(rheight + 1);
    }
}

// calculate the total value of all nodes from a given BST
int totalValueNode(Node* root)
{
    if (root == NULL)
        return 0;
    else
    {

        return root->key + totalValueNode(root->p_left) + totalValueNode(root->p_right);
    }
}
//count the number of Node from a given BST
int countNode(Node* root)
{
    if (root == NULL)
        return 0;
    else
    {

        return countNode(root->p_left) + countNode(root->p_right)+1;
    }
}

Node* Search(Node* root, int x) {
    if (root == NULL || root->key == x) {
        return root;
    }

    if (root->key < x)
        return Search(root->p_right, x);

    // Key is smaller than root's key 
    return Search(root->p_left, x);
}


void printGivenLevel(Node* root, int level)
{
    if (root == NULL)
        return;

    if (level == 1)
        cout << root->key << " ";
    else if (level > 1)
    {
        printGivenLevel(root->p_left, level - 1);
        printGivenLevel(root->p_right, level - 1);
    }
}

void LevelOrder(Node* root) {
    if (root)
        return;
    int h = height(root);
    int i;

    for (i = 1; i <= h; i++)
        printGivenLevel(root, i);
}



void insertNode(Node*& root, int x)  
{
    Node* temp = creatNode(x);
    //empty
    if (root == NULL) {
        root = temp;
        return;
    }

    //left
    if (x < root->key)
        return insertNode(root->p_left, x);
    //right
    else if (x > root->key)
        return insertNode(root->p_right, x);
    else
        return;
}

Node* LeftMostNode(Node* pRoot) {
    Node* p = pRoot;

    while (p->p_left != NULL)
        p = p->p_left;

    return p;
}

Node* RightMostNode(Node* pRoot) {
    Node* p = pRoot;

    while (p->p_right != NULL)
        p = p->p_right;

    return p;
}
void removeNode(Node*& root, int x) {
    if (root == NULL) {
        return;
    }

    //left
    if (x < root->key)
        return removeNode(root->p_left, x);
    //right
    else if (x > root->key)
        return removeNode(root->p_right, x);
    else {
        //pRoot don't have child
        if (root->p_left == NULL && root->p_right == NULL) {
            delete root;
            root = NULL;
        }//pRoot have one child 
        else if (root->p_left == NULL || root->p_right == NULL) {
            Node* p = new Node;

            p = root;

            if (root->p_left == NULL) {
                root = root->p_right;
            }
            else {
                root = root->p_left;
            }

            delete p;
        }
        else {
            //TH3: pRoot have two child
            // p = Node LeftMost of child right ???
            // p = Node RightMost of child left ???
            Node* p = RightMostNode(root->p_left);    // Find the largest node in the left 

            root->key = p->key;          // Copy value of that node
            removeNode(root->p_left, p->key);    // remove node that we had copied before
        }
    }
}

void removeTree(Node*& root)
{
    if (root == NULL)
    {
        return;
    } 

    removeTree(root->p_right);
    removeTree(root->p_left);
    delete root;
}

//Check left tree
bool isSubTreeLess(Node* root, int value) {
    if (root == NULL)
        return true;

    if (root->key <= value && isSubTreeLess(root->p_left, value) && isSubTreeLess(root->p_right, value))
        return true;
    else
        return false;
}
//Check right tree
bool isSubTreeGreater(Node* root, int value) {
    if (root == NULL)
        return true;

    if (root->key > value && isSubTreeGreater(root->p_left, value) && isSubTreeGreater(root->p_right, value))
        return true;
    else
        return false;
}
//Determine if a given Binary Tree is Binary Search Tree
bool isBST(Node* root) {
    if (root == NULL)
        return true;
    
    if (isSubTreeLess(root->p_left, root->key) && isSubTreeGreater(root->p_right, root->key)
        && isBST(root->p_left) && isBST(root->p_right))
        return true;
    else
        return false;
}