#include <iostream>
#include <queue>
using namespace std;
struct BSTNode {
	int data;
	BSTNode* left;
	BSTNode* right;

	BSTNode(int value) {
		data = value;
		left = nullptr;
		right = nullptr;
	}
};

BSTNode* insert(BSTNode* root, int key) {

	if (root == nullptr) {
		return new BSTNode(key);
	}

	if (root->data > key) root->left = insert(root->left, key);
	if (root->data < key) root-> right = insert(root -> right, key);

	return root;
}

BSTNode* minVal(BSTNode* root) {
	BSTNode* tmp = root;
	while (tmp != nullptr&&tmp->left != nullptr) tmp = tmp->left;
	return tmp;
}
BSTNode* maxVal(BSTNode* root) {
	BSTNode* tmp = root;
	while (tmp != nullptr&&tmp->right != nullptr) tmp = tmp->right;
	return tmp;
}
int wayLength(BSTNode* root,int key) {

	int wayLength = 0;
	while (root != nullptr) {

		if (root->data == key) return wayLength;
		else if (root->data < key) root = root->right;
		else root = root->left;

		wayLength++;
	}


	return -1;

}
void inOrder(BSTNode* root) {

	if (root != nullptr) {
		inOrder(root->left);
		cout << root->data << " ";
		inOrder(root->right);
	}
	return;
}

BSTNode* deleteNode(BSTNode* root, int key) {

	if (root == nullptr) return nullptr;

	if (root->data > key) root->left = deleteNode(root->left, key);
	else if (root->data < key) root->right = deleteNode(root->right, key);
	else {
		if (root->left == nullptr) {
			BSTNode* tmp = root->right;
			delete root;
			return tmp;
		}

		else if (root->right == nullptr) {
			BSTNode* tmp = root->left;
			delete root;
			return tmp;
		}

		BSTNode* tmp = minVal(root->right);
		root->data = tmp->data;
		root->right = deleteNode(root->right, tmp->data);

	}
	return root;//This is needed when trying to delete a node that does not exsist

}

int countLeftNodes(BSTNode* root) {

	if (root == nullptr || root->left == nullptr) return 0;

	if (root->right == nullptr) return 1 + countLeftNodes(root->left);
	return 1 + countLeftNodes(root->left) + countLeftNodes(root->right);
}

int countRightNodes(BSTNode* root) {

	if (root == nullptr || root->right == nullptr) return 0;

	if (root->left == nullptr) return 1 + countRightNodes(root->right);
	return 1 + countRightNodes(root->left) + countRightNodes(root->right);
}

void leftRight(BSTNode* root) {
	cout << "[" << countLeftNodes(root) << "," << countRightNodes(root) << "]\n";
}

void levelOrderTraversal(BSTNode* root) {

	if (root!=nullptr) {

		queue <BSTNode*> q;
		q.push(root);


		while (!q.empty()) {

			BSTNode* node = q.front();
			q.pop();
			cout << node->data << " ";

			if (node->left!=nullptr) q.push(node->left);
			if (node->right != nullptr) q.push(node->right);
		}
	}
}

bool checkBST(BSTNode* root, BSTNode* l = nullptr, BSTNode* r = nullptr) {

	if (root == nullptr) return true;

	if ((l != nullptr&&root->data <= l->data)
		||
		(r != nullptr&&root->data >= r->data)) return false;

	return checkBST(root->left, l, root)
		&&
		checkBST(root->right, root, r);
}

BSTNode* lca(BSTNode* root, int v1, int v2) {

	while (root != nullptr) {
		if (root->data < v1&&root->data < v2) {
			root = root->right;
		}
		else if (root->data > v1&&root->data > v2) {
			root = root->left;
		}
		else break;
	}

	return root;
}