Facebook Hacker Cup 2013 Qualification Round(Solutions)

No intro is required.

you can find the qualification round problems in the below link.

https://www.facebook.com/hackercup/problems.php?round=185564241586420

Among the three problems, Problem1 and Problem2 are very easy if you come up with the logic soon.
And the third one is straight forward question with a very good logic.

Beautiful strings:
Like every one i started thinking very straight forward for this question, i.e. I need to process the sample data first to get the key string/algorithm as it is appears to be some kind of ciphering method is behind the scenes. 

ABbCcc with the answer 152, so i thought Ca(a)=24, Ca(b)=25 and Ca(c)=26.
So I was started thinking that its Caesar Cipher with shift 24.

So i continued to the second example. Kabooooommm...I was wrong :P

Still i was checking all the ciphering algorithms i knew substitution,transposition, rotational and Affine cipher etc etc.

Wait a minute, what if characters are assigned with values such that the Beauty(a.k.a. weight) of the string is maximized....it will become more beautiful right :P

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 501

char str[MAX];

int findBeautyOfString(){
 int d[26]={0};
 int sum=0,i=0;
 while(str[i]!='\0'){
  if(isalpha(str[i])){d[tolower(str[i])-'a']++;}
  i++;
 } 
 sort(d,d+26);
 for(int i=1;i<=26;i++){sum+=i*d[i-1];} 

 return sum;
}


int main(){
 //ios_base::sync_with_stdio(false);

 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//tweak to skip first line

 for(int t=1;t<=m;t++){
  cin.getline(str,MAX); 
  printf("Case #%d: %d\n",t,findBeautyOfString());
 }

}

Balanced Smileys
Simple logic. Process the characters in forward direction and based on the result of the remaining string evaluate whether it is a balanced string or not.
Its like balanced parenthesis problem, but here we need to ensure that additional decisions have made proper if a smiley is observed.

#include<iostream>
#include<sstream>
#include<fstream>

#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

using namespace std;

#define MAX 101

char str[MAX];
int n=0;

bool balanced(int index,int right){
 if(index==n){
  if(right>0){
   return false;
  }
  return true;
 }

 if(str[index]==')' && right==0)  return false;
 if(str[index]=='(')  return balanced(index+1,right+1);
 if(str[index]==')')  return balanced(index+1,right-1);
 if(str[index]==':' && index<n-1 && (str[index+1]==')'||str[index+1]=='(')){
   return balanced(index+2,right)|balanced(index+1,right);
 }
 return balanced(index+1,right);
}


int main(){
// ios_base::sync_with_stdio(false);
 
 int m=0;
 scanf("%d",&m);
 cin.getline(str,MAX);//Tweak to skip first line due to the usage of scanf to get m.

 for(int i=1;i<=m;i++){
  cin.getline(str,MAX);
  n=strlen(str);
  printf("Case #%d: %s\n",i,(balanced(0,0)?"YES":"NO"));
 }
}

Find the Min
This is the problem in which i felt ashamed for never trying to code python.
And I came to know about the power of python.
Logic is simple but the implementation is cumbersome for this problem considering the large data set range, which will make you to go mad to think.

For this one, i have first implemented with the use of hash map in cpp.
But i adopted a brute force method to find the n elements.
For small data set it was working but when it comes to large data set, memory allocation problems(Out of memory and glibc errors as i was coding in ubuntu) etc etc.

/*
Based on Hashmap
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define INS pair<int,int>

using namespace std;


map<int,int> m1,m2;
map<int,int>::iterator it1,it2;



int findNthNumber(int n,int k,int a,int b,int c,int r){
 m1.clear();
 m2.clear();
  
 printf("FindNumber: %d %d %d %d %d %d\n",n,k,a,b,c,r); 
 m2.insert(INS(-1,-1));
 m2.insert(INS(9999999,9999));
 m1.insert(INS(0,a));
 m2.insert(INS(a,0));
 it1=m1.begin();
 for(int i=1;i<k;i++){
  m1.insert(INS(i,(((b*(*it1).second)+c)%r)));
  ++it1;
  m2.insert(INS((*it1).second,(*it1).first));
 } 
   for(;it1!=m1.end();++it1){
    cout<<(*it1).first<<"\t"<<(*it1).second<<endl;
   }

 map<int,int>::iterator min,max,del1,del2,last;
 min=max=m2.begin();
 max++;
 int i=k;
 while(i<n){ 
  while((*min).first+1==(*max).first){
   last=m2.end();
   --last;
   if(max==last){
    min=max=m2.begin();
   }else{
    min=max;
   }
   ++max;
  }
  
  while((*min).first+1<(*max).first){
   
   
   m1.insert(INS(i,(*min).first+1));
   m2.insert(INS((*min).first+1,i));
   ++min;
   
   del1=m1.find(i-k);
   del2=m2.find((*del1).second);
   
   
   m1.erase(del1);
   if(del2==min){
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if((*del2).first < (*min).first){
    min=del2;
    --min;
    m2.erase(del2);
    max=min;++max;
   }else if(del2==max){
    ++max;
    if(max==m2.end()){
     min=max=m2.begin();
     ++max;
    }
    m2.erase(del2);
   }else{
    m2.erase(del2);
   }
   
   if(i==n-1){
    last=m1.find(i);
    return ((*last).second);
   }
   i++;
  }
 }


 return 0;
}

int main(){
// ios_base::sync_with_stdio(false);
 
  
 
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  int n=0,k=0,a=0,b=0,c=0,r=0;
  scanf("%d %d\n%d %d %d %d",&n,&k,&a,&b,&c,&r); 
  if(t==3) 
  printf("Case #%d: %d\n",t,findNthNumber(n,k,a,b,c,r)); 
 }
}

Later wrote the code in python, which was working fine but still the same result with large data set. But you know what , I liked python  and it is uber kewl :D.

A pattern was observed when i printed all the elements of the array in the end for a case, in the brute force method. Tada...!! there it is :D simplified. n I have google'd to find out more about "modulo randomization".

Start with 0, keep inserting the numbers if you don't find them last k. 

if you are deleting a front number which is less than the current number inserted you are free to insert that number just after the current number. 

Otherwise increase the number and continue with the procedure.

So on the whole next k+1 elements will have numbers from 0 to k(order will be different). But the same order will be repeated again for next k+1 elements also.
so you need to determine just k+1 elements from which you can make out the nth element.

/*
Based on Array
*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<algorithm>
#include<iterator>
#include<vector>
#include<string>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cassert>

#define __int64 unsigned long long int

#define KMAX 100001
#define MAX 200001


using namespace std;

__int64 n=0ULL,k=0ULL,a=0ULL,b=0ULL,c=0ULL,r=0ULL;
__int64 m[MAX]={0ULL};
int s[MAX]={0};

__int64 findNthNumber(){
 for(int i=0;i<MAX;i++){m[i]=0ULL;s[i]=0;} 

 __int64 sMax=k+k+1ULL;
 
 m[0]=a;
 if(m[0]<sMax) s[m[0]]++;
 for(__int64 i=1;i<k;i++){m[i]=(b * m[i-1] + c)%r;if(m[i]<sMax) s[m[i]]++;}
 
 __int64 i=0,j=k;
 
 while(j<sMax){
  while(s[i]==0){
   m[j]=i;
   s[i]++;
   if(m[j-k]<sMax){
    s[m[j-k]]--;
    if(m[j-k]<i && (s[m[j-k]]<=0)){ i=m[j-k]-1;}
   }
   i++;
   j++;
   if(j==sMax){break;}
  }
  i++;
 }
 
 return (m[k + (n - k - 1) % (k + 1)]);
}

int main(){
 int T=0;
 scanf("%d",&T);
 for(int t=1;t<=T;t++){
  scanf("%llu %llu\n%llu %llu %llu %llu",&n,&k,&a,&b,&c,&r); 
  printf("Case #%d: %llu\n",t,findNthNumber()); 
 }
}

Linked List Related

Brief list of simple problems based on linked list and their solutions.
Most of them are recursive approaches and they can be written iteratively also.

1.Given a linked-list and 2 integers k & m. Reverse the linked-list till k elements and then traverse till m elements and repeat.
2.Reverse a Linked List(Recursion and Iterative methods).
3.Print Linked List in Reverse & Alternative nodes.

#include<iostream>
#include<sstream>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<vector>

using namespace std;



struct node{
 int data;
 struct node *next;
};


void push(struct node **head_first,int data){
 struct node *new_node=NULL;
 new_node=(struct node*)malloc(sizeof(struct node));
 
 new_node->data=data;
 new_node->next=(*head_first);
 *head_first=new_node;
}

void printAll(struct node *head){
 while(head!=NULL){
  cout<<head->data<<"\t";
  head=head->next;
 }
}

void printInReverse(struct node *head){
 if(head==NULL){
  return;
 }
 printInReverse(head->next);
 cout<<head->data<<"\t";
}

void printAlternative(struct node *head){
 if(head==NULL){
  return;
 }
 cout<<head->data<<"\t";
 if(head->next!=NULL){
  printAlternative(head->next->next);
 }
}

struct node* reverseListRecursion(struct node** head_first,struct node** head){
 
 struct node *curr=(*head_first);
 
 if(curr->next==NULL){
  *head=curr;
  return curr;
 }
 
 struct node **next=NULL;
 next=&(curr->next);
 
 reverseListRecursion(next,head)->next=curr;
 
  
 return curr;
}

struct node* reverseListIteration(struct node* head){
 if(head!=NULL){
  struct node* prevN=NULL;
  struct node* currN=head;
  struct node* nextN=head->next;
  
  while(nextN!=NULL){
   currN->next=prevN;
   prevN=currN;
   currN=nextN;
   nextN=nextN->next;
  }
  currN->next=prevN;
  return currN;
 }
}


struct node* reverseList(struct node** root,struct node** head,struct node** revHead,int i,int k){
    if(root==NULL && i<k){
        return NULL;
    }
    
    if(i==k){
        (*head)=(*root)->next;
 (*revHead)=(*root);
        return *root;
    }
    
    struct node* curr=*root;
    struct node* nextN=reverseList(&(curr->next),head,revHead,i+1,k);
    if(nextN!=NULL){
        nextN->next=curr;
    }else{
        return NULL;
    }
    
    if(i==1 && *head !=NULL){
        curr->next=(*head);
        return *head;
    }
    
    return curr;
}

void reverseAndTraverse(struct node *root, int k,int m){
    struct node *kNode=NULL; // K th Node - Assuming Node count from 0 :P
    struct node *revHead=NULL;

    kNode=reverseList(&root,&kNode,&revHead,1,k);
    
    if(kNode==NULL){
        printf("InSufficient Linked List\n");
        return;
    }
    
    int i=0;
    while(i<m && kNode!=NULL){
        printf("%d ",kNode->data);
        kNode=kNode->next;
 i++;
    }    

 cout<<endl; 

  while(revHead!=NULL){
  printf("%d ",revHead->data);
  revHead=revHead->next;
 }
}



int main(){
 struct node *head=NULL;
 
 push(&head,6);
 push(&head,5);
 push(&head,4);
 push(&head,3);
 push(&head,2);
 push(&head,1);
 
 
 cout<<"Printing In Normal:\t";
 printAll(head);cout<<endl;
 
 cout<<"Printing In Reverse:\t";
 printInReverse(head);cout<<endl;

 cout<<"Printing In Alternative:\t";
 printAlternative(head);cout<<endl;
 
 cout<<"Converting to Reverse:\n";
 struct node* revHead=NULL;
 reverseListRecursion(&head,&revHead)->next=NULL; 
 head=revHead;
 
 cout<<"After the Reversal-1:\t";
 printAll(head);cout<<endl;
 
 cout<<"Converting to Reverse Again:\n";
 head=reverseListIteration(head); 
 
 cout<<"After the Reversal-2:\t";
 printAll(head);cout<<endl;
 
 cout<<"Perform Reverse of K and Traversal of M \t";
 int n=1;
 scanf("%d",&n);
 reverseAndTraverse(head,n,3);cout<<endl;

 
}

Create a list of Vertical sum of a given binary tree.

A simple recursive solution would be sufficient enough to solve this.

The approach is to weight each node in the tree as below, starting with root node's weight as 0.

1. Weight of the left child of the node will be less than weight of the root by one.
2. Weight of the right child of the node will be more than weight of the root by one.

By this way the whole tree can be weighted,
and now Sum up all the nodes with same weight which gives the vertical sum of the column of nodes.

Below is implementation, and the results can be stored in either array or list or any DS.

/*
Q: Create a list of Vertical sum of a given binary tree.
*/

struct node{
 int data;
 struct node* left;
 struct node* right;
}

int getHeightOfTree(struct node* root){
 if(root==NULL){
  return -1;
 }
 int l= getHeightOfTree(root->left);
 int r= getHeightOfTree(root->right);
 return ((l>r)?(l+1):(r+1));
}


void buildVerticalSum(struct node* root, int A[], int h, int w){
 if(root!=NULL){
  buildVerticalSum(root->left,A,h,w-1);
  A[h+w]+=root->data;
  buildVerticalSum(root->right,A,h,w+1);
 }
}

/* Array A will have vertical sums of the tree. This can be modified to create a list. Or in Other DS*/
void verticalSum(struct node* root){
 int h=getHeightOfTree(root);
 
 int* A=NULL;
         A=(int*)malloc(sizeof(int)*(2*h+1));
 
 buildVerticalSum(root,A,h,0);
 
 for(int i=0;i<2*h+1;i++){
  printf(“%d ”,A[i]);
 }
 printf(“\n”); 
 
}

Given a String of Length N, find all combinations of substrings of length k(Repetition Allowed)

Print all combination of given length k possible with characters available in a given string "S" with repetition in new lines.
Again an easy recursion problem.

void printAllCombinationsOfLengthK(char in[],int n,char* out,int k,int l){
	if(k==l){
		printf("%s\n",out);
		return;
	}
	for(int i=0;i<n;i++){
		out[l]=in[i];
		printAllCombinationsOfLengthK(in,n,out,k,l+1);
	}
}

int main(){
    ios_base::sync_with_stdio(false);
	
	char* a="abcdef";
	int k=3;
	char op[k]; // Output string of length K
	
	printAllCombinationsOfLengthK(a,strlen(a),op,k,0);

    system("PAUSE");
}

Define the tree, such that the parent node always contains the sum of children nodes.

Simple. I think, no explanation is required for this.

Get summation values of right sub-tree and left sub-tree, and add them to current node's data and update.

/*Define the tree, such that the parent node always contains the sum of children nodes.*/
int sumUp(struct node *root){
 if(root==NULL){
  return 0;
 }else{
  int l=sumUp(root->left);
  int r=sumUp(root->right);
  root->data=root->data + l + r;
  return root->data;
 }
}

Change the structure of a Tree node to hold a pointer for the next in-order element (sucessor).

Idea is simple, based on Threaded Trees concept.
We need to modify Morris In-Order Traversal algorithm a little to convert the tree into a linked list, where each node's right pointer will point to its in-order successor.

There is no need to change the current tree node structure.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*Tree to InOrder list conversion*/
struct node*  MorrisInOrderConversion(struct node* root){
 struct node *curr,*pre,*head=NULL;
 
 if(root==NULL){
  return NULL;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   if(head==NULL){
    head=curr;
   }
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    struct node* next=curr->right;
    struct node* temp=curr->right;
    curr->right=NULL;
    while(next->left!=NULL){
     next=next->left;
    }
    curr->right=next;
    curr=temp;
   }
  }
 }
 
 return head; //Returns head of the converted list
}

/*Traverse the Converted list*/
void traverseList(struct node* head){
 while(head!=NULL){
  printf("%d ",head->data);
  head=head->right;
 }
}

And One more approach also exists for this, which involves creating a new list without changing current tree structure.

This can be written with Morris In-Order Tree traversal algorithm or Generic In-Order traversal algorithm.

Below is the code for generic traversal algorithm.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

/*New Node structure defined*/
struct iNode{
 struct node* pNode;
 struct iNode* successor;
};

/*Tree to InOrder List - Start */
void insertINode(struct node* p){
 struct iNode *temp = (struct iNode*)malloc(sizeof(struct iNode));
 temp->pNode=p;
 temp->successor=NULL;
 
 if(iHead==NULL){
  iHead=temp;
 }else{
  iList->successor=temp;
 }
 iList=temp; 
};

void inOrderList(struct node* root){
 if(root!=NULL){
  inOrderList(root->left);
  insertINode(root);
  inOrderList(root->right);
 }
};

void traverseIList(){
 struct iNode *curr=iHead; 
 while(curr!=NULL){
  printf("%d ",curr->pNode->data);
  curr=curr->successor;
 }
}
/*Tree to InOrder List - End */

InOrder Traversal of Tree with out using Stack and Recursion

The idea is to create links to root from predecessor node in the left sub-tree for each node.
When traversal on the current node in done, move to the right child and make that node as current node and follow the same procedure.

1. Start from the root of the current tree, as current node.
2. If current node's left Child is NULL
        print the node data.
        make right of the current node as current.
    else
        If right child of the right most node of the left sub-tree is NULL
           make it as a link to current node.
           make left of the current node as current.
        else
           print the current node data.
           make right of the current node as current.

void MorrisInOrderTraversal(struct node* root){
 struct node *curr,*pre;
 if(root==NULL){
  return;
 }
 
 curr=root;
 
 while(curr!=NULL){
  if(curr->left==NULL){
   printf("%d ",curr->data);
   curr=curr->right;
  }else{
   pre=curr->left;
   
   while(pre->right!=NULL && pre->right!=curr){
    pre=pre->right;
   }
   
   if(pre->right==NULL){
    pre->right=curr;
    curr=curr->left;
   }else{
    pre->right=NULL;
    printf("%d ",curr->data);
    curr=curr->right;
   }
  }
 }
}

Max values of Sliding Window of K, in an Array of length N(>K)

Q: An array of size N is given. Array is sub divided into sub array of size K. Find maximum value of each sub array.

It is sliding window. Let array be “1 2 3 4 5 6” and k=2
then Sub arrays {1 2},{2 3},{3 4},{4 5},{5 6}.

For all these sub arrays, maximum of each needs to found.[Array is unordered.]

struct node{ 
 int data, index; 
 struct node next; 
 struct node *prev; 
}; 

struct DQueue{ 
 struct node *front; 
 struct node *rear; 
}; 

struct DQueue createDQ(){ 
 struct DQueue* newNode=(struct DQueue*)malloc(sizeof(struct DQueue)); 
 newNode->front=newNode->rear=NULL; 
} 

bool isDQEmpty(struct DQueue* DQ){ 
 return (DQ->front==NULL); 
} 

struct node* createNode(int data,int index){ 
 struct node* newDQNode=(struct node*)malloc(sizeof(struct node)); 
 newDQNode->data=data; 
 newDQNode->index=index; 
 return newDQNode; 
} 

void pushDQFront(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  temp->next=DQ->front; 
  DQ->front->prev=temp; 
  DQ->front=temp; 
 } 
} 

void pushDQBack(struct DQueue* DQ,int data,int index){ 
 struct node* temp=createNode(data,index); 
 if(DQ->front==NULL && DQ->rear==NULL){ 
  DQ->front=DQ->rear=temp; 
 }else{ 
  DQ->rear->next=temp; 
  temp->prev=DQ->rear; 
  DQ->rear=temp; 
 } 
} 

void popDQFront(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->front; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->front->next->prev=NULL; 
  DQ->front=DQ->front->next; 
  temp->next=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

void popDQBack(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return; 
 } 
 struct node* temp=DQ->rear; 
 if(DQ->front==DQ->rear){ 
  DQ->front=DQ->rear=NULL; 
 }else{ 
  DQ->rear->prev->next=NULL; 
  DQ->rear=DQ->rear->prev; 
  temp->prev=NULL; 
 } 
 free(temp); 
 temp=NULL; 
} 

struct node* frontOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->front; 
} 

struct node* rearOfDQ(struct DQueue* DQ){ 
 if(isDQEmpty(DQ)){ 
  return NULL; 
 } 
 return DQ->rear; 
} 

void maxSlidingWindow(int a[],int n,int k){ 
 int i; 
 struct DQueue* DQ=createDQ(); 

 for(i=0;i<k;i++){ 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
 } 
 printf("%d",frontOfDQ(DQ)->data); 

 for(;i<n;i++){ 
  while(!isDQEmpty(DQ) && frontOfDQ(DQ)->index <= i-k){ 
   popDQFront(DQ); 
  } 
  while(!isDQEmpty(DQ) && a[i] >= rearOfDQ(DQ)->data){ 
   popDQBack(DQ); 
  } 
  pushDQBack(DQ,a[i],i); 
  printf("%d",frontOfDQ(DQ)->data); 
 } 
} 

int main(){ 
 int a[]={3,5,2,8,2,3,7,9,2,2,44,66,2,23,4,54,2}; 
 int n=sizeof(a)/sizeof(a[0]); 
 int k=4; 
 maxSlidingWindow(a,n,k); 
 system("PAUSE"); 
}

Find two elements which will sum up to a given value, in a Sorted Array.

Given sorted integer array and a given value we have to find two elements which will sum up to a given value.

Since it is a sorted array our job is so easy.

For example, array a is having n element in sorted order
A[0]<A[1]<A[2]<........<A[n-1];

From this we can deduce that,
A[0]+A[1]<A[0]+A[2]<A[0]+A[3].......;
A[0]+A[n-1]<A[1]+A[n-1]<.....<A[n-2]+A[n-1];

Compare from the extreme summations with the given value and increase or decrease the indexes according to the comparison.

Int a[SIZE];
Int a[SIZE];
int n;

void findTwoElementsToN(int a[],int n){
 int i=0;
 int j=sizeof(a)/sizeof(int) -1;
 int sum=0;

 if(i<j){
  sum=a[i]+a[j];
  if(sum<n){
   i++;
  }else if(sum>n){
   j--;
  }else{
    printf(“%d and %d”,a[i],a[j]);
  }
 }
}

Least Common Ancestor of two nodes in a Given Unordered Tree.

There can be three possibilities for finding LCA is a tree.
1. Both nodes belong to left sub-tree.
2. Both nodes belong to right sub-tree.
3. One per each sub-tree.
 In fact 4th possibility is also there, i.e. nodes are not at all present in the tree.

In the first case, Current node can't be the LCA because an CA exist in the left sub-tree.
Similarly, in the second case, Current node can't be the LCA because an CA exist in the right sub-tree.
In the third case, Current node will be the LCA.

struct node{
 int data;
 struct node* left;
 struct node* right;
};

struct node* leastCommonAncestor(struct node* root,struct node* p,struct node* q){
 
 if(root==NULL){
  return NULL;  //If no root  leastCommonAncestor is NULL.
 }

 if(root==p || root==q){
  return root; // Check if the current root is equal to any of the desired node.
 }else{
  struct node* l=leastCommonAncestor(root->left, p, q); // Find LCA in left of the tree
  struct node* r=leastCommonAncestor(root->right, p, q); // Find LCA in right of the tree
  
  if(l!=NULL && r!=NULL){
   return root; 
  }else if(l!=NULL && r==NULL){
   return l;
  }else if(l==NULL && r!=NULL){
   return r;
  }else{
   return NULL;
  }
 } 
}

Binary Tree Related

Code for the following Questions can be found in below code.

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder, PreOrder, PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

/*
Written By BrOkEN@!

Q: Given a node of Binary Tree . find all node's at distance k from it .
Q: Simple InOrder,PreOrder,PostOrder Traversals of the Tree.
Q: Given a node in the Tree. Find path from the root of tree to the node.
Q: Given a node in the Tree. Find the height of the node from the root.

*/

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>

#define INFINITE 1000000

using namespace std;

struct node{
 int data;
 struct node* left;
 struct node* right;
};

struct trackNode{
 struct node* pNode;
 struct trackNode* parent;
};

struct trackNode *list=NULL,*head=NULL;

void insertTrackNode(struct node* p){
 struct trackNode *temp = (struct trackNode*)malloc(sizeof(struct trackNode));
 temp->pNode=p;
 
 if(list==NULL){
  head=temp;
 }else{
  list->parent=temp;
 }
 list=temp; 
};

/*Find path from root to Specific Node*/
bool trackPath(struct node *root, struct node *p){
 
 if(root==NULL){
  return false;
 }
 
 if(root==p){
  insertTrackNode(root);
  return true;
 }else{
  if(trackPath(root->left,p)||trackPath(root->right,p)){
   insertTrackNode(root);
   return true;
  }else{
   return false;
  }
 }
};

/*Constructing a tree and returning the root*/
struct node* buildTree(){
 struct node* n01=(struct node*) malloc(sizeof(struct node));n01->data=1;
 struct node* n02=(struct node*) malloc(sizeof(struct node));n02->data=2;
 struct node* n03=(struct node*) malloc(sizeof(struct node));n03->data=3;
 struct node* n04=(struct node*) malloc(sizeof(struct node));n04->data=4;
 struct node* n05=(struct node*) malloc(sizeof(struct node));n05->data=5;
 struct node* n06=(struct node*) malloc(sizeof(struct node));n06->data=6;
 struct node* n07=(struct node*) malloc(sizeof(struct node));n07->data=7;
 struct node* n08=(struct node*) malloc(sizeof(struct node));n08->data=8;
 struct node* n09=(struct node*) malloc(sizeof(struct node));n09->data=9;
 struct node* n10=(struct node*) malloc(sizeof(struct node));n10->data=10;
 struct node* n11=(struct node*) malloc(sizeof(struct node));n11->data=11;
 struct node* n12=(struct node*) malloc(sizeof(struct node));n12->data=12;
 struct node* n13=(struct node*) malloc(sizeof(struct node));n13->data=13;
 struct node* n14=(struct node*) malloc(sizeof(struct node));n14->data=14;
 struct node* n15=(struct node*) malloc(sizeof(struct node));n15->data=15;
 
 n08->left=n04;n08->right=n12;
 
 n04->left=n02;n04->right=n06;
 n02->left=n01;n02->right=n03;
 n06->left=n05;n06->right=n07;
 
 n12->left=n10;n12->right=n14;
 n10->left=n09;n10->right=n11;
 n14->left=n13;n14->right=n15;
 
 n01->left=n01->right=NULL;
 n03->left=n03->right=NULL;
 n05->left=n05->right=NULL;
 n07->left=n07->right=NULL;
 n09->left=n09->right=NULL;
 n11->left=n11->right=NULL;
 n13->left=n13->right=NULL;
 n15->left=n15->right=NULL;

 
 return n08;
};

/*InOrder Traversal of Tree with root Node*/
void inOrder(struct node* root){
 if(root!=NULL){
  inOrder(root->left);
  printf("%d ",root->data);
  inOrder(root->right);
 }
};

/*PreOrder Traversal of Tree with root Node*/
void preOrder(struct node* root){
 if(root!=NULL){
  printf("%d ",root->data);
  preOrder(root->left);
  preOrder(root->right);
 }
};

/*PostOrder Traversal of Tree with root Node*/
void postOrder(struct node* root){
 if(root!=NULL){
  postOrder(root->left);
  postOrder(root->right);
  printf("%d ",root->data);
 }
};


/*Find Nodes at distance K from the root(possibility to skip subtree is also provided.)*/
void findNodesAtDistanceK(struct node *root,int k,bool left,bool right){
 
 
 if(root!=NULL){
  if(k==0){
   printf("%d ",root->data);
   return;
  }
  
  if(left==true && right==false){
   findNodesAtDistanceK(root->left,k-1,true,true);
  }else if(left==false && right==true){
   findNodesAtDistanceK(root->right,k-1,true,true);
  }else{
   findNodesAtDistanceK(root->left,k-1,true,true);
   findNodesAtDistanceK(root->right,k-1,true,true);
  }
 }
}

/*Get Height of the node*/
int getHeight(struct node* root,struct node* p){
 
 if(root==NULL){
  return INFINITE;
 }
 
 if(root==p){
  return 0;
 }else{
  int l=1+getHeight(root->left,p);
  int r=1+getHeight(root->right,p);
  if(l>r){
   return r;
  }else{
   return l;
  }
 }
}


int main(){
 int k=3;//Distance
 struct node *root=NULL;
 root=buildTree();
 
 struct node* p=root->right->left->right; //get a random node from Tree

 if(trackPath(root,p)){
  int i=0;
  struct trackNode* prev=NULL;
  while(head!=NULL && i<=k){

   if(prev==NULL){
    findNodesAtDistanceK(head->pNode,k-i,true,true);
   }else{
    findNodesAtDistanceK(head->pNode,k-i,head->pNode->left!=prev->pNode,head->pNode->right!=prev->pNode);
   }
   
   prev=head;
   head=head->parent;
   i++;
  }
 }

 system("PAUSE");
}