lca in binary tree

Least Common Ancestor(LCA) in a tree is defined as the first node that comes common for both the given nodes while travelling towards the root. Write an efficient function “TreeNode FindLca(TreeNode t, TreeNode p, TreeNode q)” to find the least common ancestor of nodes p and q in a binary tree t. You are not allowed to modify the structure of tree node.

 What are the time and space complexities of your solution? Assume that p and q points to valid nodes in a given binary tree. 

Input:

      3                                      p=ADDR(9) q=ADDR(8)
    /    \
  4      7
 /  \    /  \
5  1  6   8
       /
     9                           

Return value: ADDR(7)

Code:

 #include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;
//building tree

struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4;
    root=(struct treenode *)malloc(sizeof(struct treenode));
    temp1=(struct treenode *)malloc(sizeof(struct treenode));
    temp2=(struct treenode *)malloc(sizeof(struct treenode));
    temp3=(struct treenode *)malloc(sizeof(struct treenode));
    temp4=(struct treenode *)malloc(sizeof(struct treenode));
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=temp4->right=NULL;
      temp2->left=temp2->right=NULL;
  printf("tree buildedsuccessfull");
       return root;
}

//this for given value find address which having those values
struct treenode * findaddress1(struct treenode *root,int i)
{
    if(root==NULL) return NULL;
    if(root->data==i) return root;
    root->left=findaddress1(root->left,i);
    root->right=findaddress1(root->right,i);
    if(root->left!=NULL)
    return root->left;
    else if(root->right!=NULL)
    return root->right;
    else return NULL;
  
}

//finding lca
struct treenode * lcabinary(struct treenode *root,int i,int j)
{
    struct treenode *rh,*lh;
    if(root==NULL) return NULL;
  
    if(root->data==i) return root;
    if(root->data==j) return root;
  
    lh=lcabinary(root->left,i,j);
    rh=lcabinary(root->right,i,j);
  
  
    if(lh!=NULL&&rh!=NULL) return root;
    else if(lh!=NULL) return lh;
    else if(rh!=NULL) return rh;
    else if(lh==NULL&&rh==NULL) return NULL;
  
  
}
void preorder(struct treenode *root)
{
    if(root==NULL)
    return;
  
   printf("%d|%u     ",root->data,root);//this for our reference
    preorder(root->left);
    preorder(root->right);
}

void main()
{
    int i,k=1,j;
    struct treenode *root,*temp1,*temp2,*temp;
    while(k)
    {
        printf("\n enter 1 to build tree");
        printf("\n enter 2 to print in preorder");
        printf("\n enter 3 to find lca");
        scanf("%d",&k);
        switch(k)
        {
            case 1:
                root=buildtree();
                break;
              
            case 2:
                preorder(root);
                break;
          
            case 3:
              
                printf("enter value of address 1");
                scanf("%d",&i);
                    printf("enter value of address 2");
                scanf("%d",&j);
                temp=lcabinary(root,i,j);
                printf("lca is %u and data %d ",temp,temp->data);
            }
        }
}