#include <iostream>

using namespace std;

class Node {
public:
int data;
Node* left;
Node* right;
int height;

Node(int v)
{
data = v;
left = NULL;
right = NULL;
height = 1;
}
};

class AVLTree {
public:
Node* root;

AVLTree()
{
root = NULL;
}

int getHeight(Node* root)

{
if (root == NULL)
{
return 0;
}
return root->height;
}

int getBalance(Node* root)

{
if (root == NULL)
{
return 0;
}
return getHeight(root->left) - getHeight(root->right);
}

int max(int a, int b)

{
if (a > b)
{
return a;
}
else
{
return b;
}
}

Node* rightRotate(Node* y)
{
Node* x = y->left;
Node* T2 = x->right;

x->right = y;
y->left = T2;

y->height = 1 + max(getHeight(y->left), getHeight(y->right));

x->height = 1 + max(getHeight(x->left), getHeight(x->right));

return x;
}

Node* leftRotate(Node* x)
{
Node* y = x->right;
Node* T2 = y->left;

y->left = x;
x->right = T2;

x->height = 1 + max(getHeight(x->left), getHeight(x->right));

y->height = 1 + max(getHeight(y->left), getHeight(y->right));

return y;
}

Node* insert(Node* root, int key)

{
if (root == NULL)
{
return new Node(key);
}

if (key < root->data)

 {
root->left = insert(root->left, key);
}
else if (key > root->data)
{
root->right = insert(root->right, key);
}
else
{
return root;
}

root->height = 1 + max(getHeight(root->left), getHeight(root->right));

int balance = getBalance(root);

if (balance > 1 && key < root->left->data)

{
return rightRotate(root);
}

if (balance < -1 && key > root->right->data)

{
return leftRotate(root);
}

if (balance > 1 && key > root->left->data)

{
root->left = leftRotate(root->left);
return rightRotate(root);
}

if (balance < -1 && key < root->right->data)

{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

void insert(int key)

{
root = insert(root, key);
}

int CountNodes(Node* root)

 {
if (root == NULL)
{
return 0;
}
return 1 + CountNodes(root->left) + CountNodes(root->right);
}
};

int main()
{

return 0;
}

FUNCTION 1 --> ISBST( )

bool IsBST()
{
return IsBSTree(root, NULL, NULL);
}

bool IsBSTree(Node* root, Node* min, Node* max)

{
if (root == NULL)
{
return true;
}

if (min != NULL && root->data <= min->data)

{
return false;
}

if (max != NULL && root->data >= max->data)

{
return false;
}

return IsBSTree(root->left, min, root) && IsBSTree(root->right, root, max);

}

FUNCTION --> 2 GETRANK( )

int GetRank2(Node* root, int key)
{
if (root == NULL)
{
return 0;
}

if (key < root->data)

{
return GetRank2(root->left, key);
}
else if (key > root->data)
{
int leftCount = CountNodes(root->left);
return 1 + leftCount + GetRank2(root->right, key);
}
else
{
return CountNodes(root->left) + 1;
}
}

int GetRank(Node* root, int key)

{
return GetRank2(root, key);
}

FUNCTION --> 3 INVERT( )

void Invert()
{
InvertTree(root);
}

void InvertTree(Node* root)

{
if (root == NULL)
{
return;
}

Node* temp = root->left;

root->left = root->right;
root->right = temp;

InvertTree(root->left);
 InvertTree(root->right);
}

FUNCTION --> 4 LOWEST COMMON ANCESTOR

Node* FindLCA(Node* root, int a, int b)

{
if (root == NULL)
{
return NULL;
}

if (a < root->data && b < root->data)

{
return FindLCA(root->left, a, b);
}

if (a > root->data && b > root->data)

{
return FindLCA(root->right, a, b);
}

return root;
}

int LowestCommonAncestor(int a, int b)

{
Node* temp = FindLCA(root, a, b);
if (temp)
{
return temp->data;
}
else
{
return -1;
}
}

FUNCTION --> 5 LONGEST CONSECTIVE PATH

int LongestConsecutivePath()
{
int maxLen = 0;
LongestConsecutivePathHelper(root, maxLen);
return maxLen;
}
void LongestConsecutivePathHelper(Node* root, int& maxLen)
{
if (root == NULL)
{
return;
}

int inc = 1;
int dec = 1;

if (root->left)
{
LongestConsecutivePathHelper(root->left, maxLen);

if (root->data == root->left->data + 1)
{
dec = getDecreasingPath(root->left) + 1;
}
else if (root->data == root->left->data - 1)
{
inc = getIncreasingPath(root->left) + 1;
}
}

if (root->right)
{
LongestConsecutivePathHelper(root->right, maxLen);

if (root->data == root->right->data + 1)
{
dec = max(dec, getDecreasingPath(root->right) + 1);
}
else if (root->data == root->right->data - 1)
{
inc = max(inc, getIncreasingPath(root->right) + 1);
}
}

maxLen = max(maxLen, inc + dec - 1);

}

int getIncreasingPath(Node* root)

{
if (root == NULL)
{
return 0;
 }

int left = 0, right = 0;

if (root->left && root->data + 1 == root->left->data)

{
left = getIncreasingPath(root->left);
}
if (root->right && root->data + 1 == root->right->data)
{
right = getIncreasingPath(root->right);
}

return 1 + max(left, right);

}

int getDecreasingPath(Node* root)

{
if (root == NULL)
{
return 0;
}

int left = 0;
int right = 0;

if (root->left && root->data - 1 == root->left->data)

{
left = getDecreasingPath(root->left);
}
if (root->right && root->data - 1 == root->right->data)
{
right = getDecreasingPath(root->right);
}

return 1 + max(left, right);

}

FUNCTION 6 --> GETCOUSINS( )

void GetCousins(int key)
{
int targetLevel = GetLevel(root, key, 0);
Node* parent = FindParent(root, key, NULL);

if (targetLevel == -1)
{
 cout << "Key not found.\n";
return;
}

cout << "Cousins of " << key << ": ";

PrintCousins(root, key, parent, 0, targetLevel);
cout << endl;
}

int GetLevel(Node* root, int key, int level)

{
if (root == NULL)
{
return -1;
}

if (root->data == key)
{
return level;
}

int left = GetLevel(root->left, key, level + 1);

if (left != -1)
{
return left;
}

return GetLevel(root->right, key, level + 1);

}

Node* FindParent(Node* root, int key, Node* parent)

{
if (root == NULL)
{
return NULL;
}

if (root->data == key)
{
return parent;
}

Node* left = FindParent(root->left, key, root);

if (left)
{
return left;
}
 return FindParent(root->right, key, root);
}

void PrintCousins(Node* root, int key, Node* parent, int level, int targetLevel)
{
if (root == NULL)
{
return;
}

if (level == targetLevel)
{
if (root != parent && root->data != key)
{
cout << root->data << " ";
return;
}
}

PrintCousins(root->left, key, parent, level + 1, targetLevel);

PrintCousins(root->right, key, parent, level + 1, targetLevel);
}

FUNCTION 7 --> LEVEL ORDER TRAVERSAL

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

Node* queue[100];
int front = 0;
int rear = 0;

queue[rear++] = root;

while (front < rear)

{
Node* current = queue[front++];
cout << current->data << " ";

if (current->left)
{
queue[rear++] = current->left;
 }
if (current->right)
{
queue[rear++] = current->right;
}
}
}

FUNCTION --> 8 CHECKFULLTREE ( )

bool IsFullTree(Node* root)
{
if (root == NULL)
{
return true;
}

if (root->left == NULL && root->right == NULL)

{
return true;
}

if (root->left && root->right)

{
return IsFullTree(root->left) && IsFullTree(root->right);
}

return false;
}

FUNCTION --> 9 MERGETREE( )

void StoreInOrder(Node* root, int arr[], int& index)

{
if (root == NULL)
{
return;
}

StoreInOrder(root->left, arr, index);

arr[index++] = root->data;
StoreInOrder(root->right, arr, index);
}

void MergeArrays(int arr1[], int size1, int arr2[], int size2, int
merged[], int mergedSize)
{
 int i = 0, j = 0, k = 0;

while (i < size1 && j < size2)

{
if (arr1[i] < arr2[j])
{
merged[k++] = arr1[i++];
}
else
{
merged[k++] = arr2[j++];
}
}

while (i < size1)

merged[k++] = arr1[i++];

while (j < size2)

merged[k++] = arr2[j++];

mergedSize = k;
}

Node* SortedArrayToAVL(int arr[], int start, int end)

{
if (start > end)
{
return NULL;
}

int mid = (start + end) / 2;

Node* node = new Node{ arr[mid], NULL, NULL};

node->left = SortedArrayToAVL(arr, start, mid - 1);

node->right = SortedArrayToAVL(arr, mid + 1, end);

return node;
}

void Merge(AVLTree& otherTree)

{
int arr1[1000], arr2[1000], merged[2000];
int size1 = 0, size2 = 0, mergedSize = 0;

StoreInOrder(this->root, arr1, size1);

StoreInOrder(otherTree.root, arr2, size2);

MergeArrays(arr1, size1, arr2, size2, merged, mergedSize);

 this->root = SortedArrayToAVL(merged, 0, mergedSize - 1);
}

FUNCTION --> 10 DeleteNodesGreaterThan( )

void DeleteNodesGreaterThan(int value)

{
root = DeleteGreaterThanHelper(root, value);
}

Node* DeleteGreaterThanHelper(Node* node, int value)

{
if (node == NULL)
{
return NULL;
}

node->left = DeleteGreaterThanHelper(node->left, value);

node->right = DeleteGreaterThanHelper(node->right, value);

if (node->data > value)

{
Node* temp = node->left;
delete node;
return temp;
}

return node;
}

FUNCTION --> 11 CONTAINSINDENTICALSUBTREE( )

bool ContainsIdenticalSubtrees()
{
vector<string> subtrees;
return CheckIdenticalSubtrees(root, subtrees);
}

bool CheckIdenticalSubtrees(Node* root, vector<string>& subtrees)

{
if (root == NULL)
{
return false;
 }

bool leftHas = CheckIdenticalSubtrees(root->left, subtrees);

bool rightHas = CheckIdenticalSubtrees(root->right, subtrees);

string subtree = to_string(root->data);

if (root->left)
{
subtree += "(" + to_string(root->left->data) + ")";
}
else
{
subtree += "()";
}

if (root->right)
{
subtree += "(" + to_string(root->right->data) + ")";
}
else
{
subtree += "()";
}

for (int i = 0; i < subtrees.size(); i++)

{
if (subtrees[i] == subtree)
{
return true;
}
}

subtrees.push_back(subtree);

return leftHas || rightHas;

}

FUNCTION --> 12 PruneTree( )

void PruneTree(int maxDepth)

{
root = PruneTreeHelper(root, 0, maxDepth);
}
Node* PruneTreeHelper(Node* root, int currentDepth, int maxDepth)
{
if (root == NULL)
{
return NULL;
}

if (currentDepth == maxDepth)
{
DeleteSubtree(root->left);
DeleteSubtree(root->right);
root->left = NULL;
root->right = NULL;
return root;
}

root->left = PruneTreeHelper(root->left, currentDepth + 1, maxDepth);

root->right = PruneTreeHelper(root->right, currentDepth + 1, maxDepth);

return root;
}

void DeleteSubtree(Node* root)

{
if (root == NULL)
{
return;
}

DeleteSubtree(root->left);
DeleteSubtree(root->right);
delete root;
}

FUNCTION --> 13 FindNthInTraversalOrder( )

const int IN_ORDER = 1;
const int PRE_ORDER = 2;
const int POST_ORDER = 3;

int FindNthInTraversalOrder(int n, int orderType)

{
int count = 0;
int result = -1;
 if (orderType == IN_ORDER)
{
FindNthInOrder(root, n, count, result);
}
else if (orderType == PRE_ORDER)
{
FindNthPreOrder(root, n, count, result);
}
else if (orderType == POST_ORDER)
{
FindNthPostOrder(root, n, count, result);
}

return result;
}

void FindNthInOrder(Node* root, int n, int& count, int& result)

{
if (root == NULL || count >= n)
{
return;
}

FindNthInOrder(root->left, n, count, result);

count++;
if (count == n)
{
result = root->data;
return;
}

FindNthInOrder(root->right, n, count, result);

}

void FindNthPreOrder(Node* root, int n, int& count, int& result)

{
if (root == NULL || count >= n)
{
return;
}

count++;
if (count == n)
{
result = root->data;
return;
 }

FindNthPreOrder(root->left, n, count, result);

FindNthPreOrder(root->right, n, count, result);
}

void FindNthPostOrder(Node* root, int n, int& count, int& result)

{
if (root == NULL || count >= n)
{
return;
}

FindNthPostOrder(root->left, n, count, result);

FindNthPostOrder(root->right, n, count, result);

count++;
if (count == n)
{
result = root->data;
return;
}
}

FUNCTION --> 14 FindParentOfNode( )

Node* FindParentOfNode(int key)
{
return FindParentHelper(root, NULL, key);
}

Node* FindParentHelper(Node* current, Node* parent, int key)

{
if (current == NULL)
{
return NULL;
}

if (current->data == key)
{
return parent;
}

if (key < current->data)

{
 return FindParentHelper(current->left, current, key);
}
else
{
return FindParentHelper(current->right, current, key);
}
}

FUNCTION --> 15 FindParentOfNode( )

string GetTreeSkewType()
{
int leftCount = CountNodes(root->left);
int rightCount = CountNodes(root->right);

int diff;
if (leftCount > rightCount)
{
diff = leftCount - rightCount;
}
else
{
diff = rightCount - leftCount;
}

int total = leftCount + rightCount;

if (total == 0)
{
return "BALANCED";
}

// If the difference is more than 20% of total nodes, it's skewed

if (diff * 100 > total * 20)
{
if (leftCount > rightCount)
{
return "LEFT_SKEWED";
}
else
{
return "RIGHT_SKEWED";
}
}
 return "BALANCED";
}