Lowest Common Ancestor

lca.c

#include<bits/stdc++.h>

using namespace std;

struct Node {
int data;
struct Node * right, * left;
};
void insert(Node ** tree, int val)
{
    Node *temp = NULL;
    if(!(*tree))
    {
        temp = (Node *)malloc(sizeof(Node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }

    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }

}




Node* LCA(Node *root, int , int );

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        Node *root;
        Node *tmp;
    //int i;

        root = NULL;

        int N;
        cin>>N;
        for(int i=0;i<N;i++)
        {
            int k;
            cin>>k;
            insert(&root, k);

        }

        int l,r;
        cin>>l>>r;

        cout<<LCA(root,l,r)->data<<endl;
    }
}
/*The structure of a BST Node is as follows:
struct Node {
    int data;
    Node * right, * left;
};*/

/*You are required to complete
this function*/
Node* LCA(Node *root, int n1, int n2)
{
    if(root) {
        if(root->data == n1 || root->data == n2) {
            // found lca
            return root;
        }
        Node *l = NULL, *r = NULL;
        if(n1 < root->data || n2 < root->data) {
            l = LCA(root->left, n1, n2);
        }
        if(n1 > root->data || n2 > root->data) {
            r = LCA(root->right, n1, n2);
        }
        if(r && l) {
            // I'm the LCA
            return root;
        }
        else if(l) {
            return l;
        }
        else 
            return r;
    }
    return NULL;
}