using namespace std;
class Node
{
public:
int data;
Node *right;
Node *left;
Node(int d)
{
this->data = d;
this->left = NULL;
this->right = NULL;
}
};
class custom
{
public:
bool haskeyP;
bool haskeyQ;
Node node;
custom helper(Node *root, Node *p, Node *q)
{
//base case
if (root == NULL)
{
return NULL;
}
custom *leftans = helper(root->left, p, q);
if (leftans != NULL && leftans->node != NULL)
{
return leftans;
}
custom *rightans = helper(root->right, p, q);
if (rightans != NULL && rightans->node != NULL)
{
return rightans;
}
custom *result = new custom();
if (rightans != NULL && leftans != NULL)
{
result->node = root;
result->haskeyP = true;
result->haskeyQ = true;
return result;
}
else if (root->data == p->data)
{
result->haskeyP = true;
if (leftans)
{
if (leftans->haskeyQ)
{
result->haskeyQ = true;
}
else
{
result->haskeyQ = false;
}
}
if (rightans)
{
if (rightans->haskeyQ)
{
result->haskeyQ = true;
}
else
{
result->haskeyQ = false;
}
}
if (result->haskeyP && result->haskeyQ)
{
result->node = root;
}
return result;
}
else if (root->data == q->data)
{
result->haskeyQ = true;
if (leftans)
{
if (leftans->haskeyP)
{
result->haskeyP = true;
}
else
{
result->haskeyP = false;
}
}
if (rightans)
{
if (rightans->haskeyP)
{
result->haskeyP = true;
}
else
{
result->haskeyP = false;
}
}
if (result->haskeyP && result->haskeyQ)
{
result->node = root;
}
return result;
}
}
void lca(Node *root, Node*p, Node *q)
{
custom *result = helper(root, p, q);
if (result->node != NULL)
{
cout <<"LCA: "<< result->node->data<<endl;
}
else
{
cout << "NO LCA found"<<endl;
}
}
};
Node *buildTree(int *arr, int start, int end)
{
if (start > end)
{
return NULL;
}
int mid = (start + end) / 2;
Node *root = new Node(arr[mid]);
root->left = buildTree(arr, start, mid - 1);
root->right = buildTree(arr, mid + 1, end);
return root;
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int n = sizeof(arr) / sizeof(int);
Node *root = buildTree(arr, 0, n - 1);
//cout << root->data;
custom c;
Node *p = root;
Node *q = root->right;
c.lca(root, p, q);
return 0;
}