Copy the linked list which has the random pointer and it points to any node in linked list .

The solution is to use copy-merge-split . First copy the nodes and create a new list . Then merge the nodes into the original list .Assume that ur original list is 1->2->3->NULL and u have copied the list and merged it into the orginal list . so the list will look like this 1->1->2->2->3->3->NULL . Then for the random pointer , the even nodes random pointer should point to the odd node's random->next pointer . Then separate the odd and even nodes .

Code is given below . Please let me know if there is any mistake in the code .

Code :(in C)
The node structure is given below .
struct node
{
int data;
struct node* next;
struct node* random;
}

struct node* copy_list_with_random_pointer(struct node * head)
{
//copy list and don't worry about random pointer now
struct node* copied_list_head=copy_list(head);
if(copied_list_head==NULL)
return NULL;
//merge the copied list into original list
struct node* original_list,copied_list,temp,temp1;
original_list=head;
copied_list=copied_list;
while(original_list!=NULL)
{
temp=original_list;
original_list=original_list->link;
temp->link=copied_list;

temp1=copied_list;
copied_list=copied_list->link;
temp1->link=original_list;
}

//set the random pointer for copied list
temp=head;
while(temp!=NULL)
{
temp->link->random=temp->random->next;
temp=temp->link->link;
}
 
       //split the list
original_list=head;
copied_list=head->link;
while(original_list!=null)
{
original_list->link=copied_list->link;
original_list=copied_list->link;
if(original_list!=NULL)
{
copied_list->link=original_list->link;
copied_list=original_list->link;
}
else
copied_list->link=NULL;

}

return copied_list_head;
}

//function to copy the the linked list
struct node* copy_list(struct node * head)
{
if(head==NULL)
return NULL;
struct node* temp,new_head=NULL,tail=NULL;
temp=head;
while(temp!=NULL)
{
struct node* node=malloc(sizeof(struct node*));
if(new_head==NULL)
new_head=node;
if(tail!=NULL)
tail->link=node;

               tail=node;

node->data=temp->data;
temp=temp->link;
}
tail->link=null;
return new_head;
}

Find the Immediate Ancestor of a node

There are two ways by which we can find the immediate ancestor of the node . One way is same like Lowest Common Ancestor Problem . The other way is suggested by my friend ,that's almost the same idea . But the style of coding is different . I really liked the second Method .

1st Method:(in C)

struct node * immediateAncestor(struct node *root,struct node *node)
{
if(root==NULL)
return NULL;
if(root->left==node || root->right==node)
return root;
else
{
struct node* left,right;
left=immediateAncestor(root->left,node);
right=immediateAncestor(root->right,node);
return (left!=NULL)?left:right;
}
}

2nd Method:(in C++)

node* ancestor(node *root, node *x)
{
if(root == NULL || x==NULL || root == x)
return NULL;
if(root->left==x || root->right==x)
return root;
return (ancestor(root->left,x)||ancestor(root->right,x));
}

Swap alternate nodes in a singly linked list

The concept is very easy . But you need to handle all test cases. One of the important test case is before assigning the odd_node->link to even_node , you should check whether it is NULL or NOT . Otherwise it will cause Segmentation Fault .

Code:

struct node* swap_alternate_nodes(struct node* head)
{
struct node* odd_node,even_node,temp;
if(head==NULL)
return NULL;
odd_node=head;
even_node=head->link;
if(head->link!=NULL)
head=head->link;
while(odd_node && even_node)
{
temp=even_node->link;
even_node->link=odd_node;
odd_node->link=temp;
              odd_node=temp;
if(odd_node!=NULL)
even_node=odd_node->link;
}
return head;
}

Input :   1->2->3->4->5->NULL
Output: 2->1->4->3->->5->NULL

Find Kth Largest number in a Binary Search Tree

There are two ways to find Kth Largest number in a Binary Search Tree . One is by counting the nodes in the Left side and finding the element. The second  is by using inorder traversal and static variable .

1st Method:

int FindKth(struct node* node,int k)

{

int countLeft;

countLeft=size(node->left);

if(countLeft+1==k)

return node->data;

else if(countLeft+1>k)

return FindKth(node->left,k);

else

return FindKth(node->right,k-countLeft-1);

}

//function to find the size of the binary tree.

int size(struct node* node)

{

if(node==null)

return 0;

else

return 1+size(node->left)+size(node->right);

}

2nd Method:

//different approach using inorder traversal and static variable

int FindKth(struct node* node,int k)

{

static int i=0;

if(node!=null)

{

FindKth(node->left,k);

i++;

if(i==k)

return node->data;

FindKth(node->right,k);

}

}

IsoMorphic Binary Trees

Two trees can be called isomorphic if they have similar structure and the only difference amongst them can be is, that their child nodes may or may not be swapped..

For example

The trees in the above picture are called  Isomorphic Trees.The following code checks whether two trees are Isomorphic or not.

Code:(Written in C)

int is_isomorphic(struct node *t1,struct node *t2)
{
if(t1==NULL && t2==NULL)
            return 1;
if(t1==NULL || t2==NULL || t1->data!=t2->data)
return 0;
return  (is_isomorphic(t1->left,t2->left)&&is_isomorphic(t1->right,t2->right) || is_isomorphic(t1->left,t2->right)&&is_isomorphic(t1->right,t2->left) );
}

Please let me know if u have any questions

Program to find Lowest Common Ancestor of two nodes

To find a Lowest or Least Common Ancestor of binary tree we need to pass three arguments .Those are root node of binary tree and the node details to find common ancestor (here node data's are used) . The following code recursively searches for the nodes that we need to find. When it finds the node it returns the node. If both the left and right side of the node returns the node this is it(the node is called as common ancestor) .Else the process will continue until it finds the common ancestor.

For an Example 
In the following tree
                 10
               /      \
             5         12
           /   \
         3      8
                /
               7

for nodes 7 and 3 LCA(Lowest Common Ancestor) is 5.

Code (Written in C):
struct node* lowestCommonAncestor(struct node* node, int n1,int n2)
{
if(node==NULL)
return NULL;

if(node->data==n1 || node->data ==n2)
return node;
else
{
struct node* left,right;
left=lowestCommonAncestor(node->left,n1,n2);
right=lowestCommonAncestor(node->right,n1,n2);

if(left&&right)
return node;
else
return left==NULL?right:left;
}
}

Efficient java program to find GCD of given two numbers

The following java code finds the biggest common factor(GCD) for two numbers easily. Otherwise we need to check it from smallest number.Lets assume that the smallest number is n. So we need to check it from n,n-1....1 to find the common factor.But here out of two inputs set the biggest one to b. Then find the common factor using the % operator and keep changing the values of a and b until you find the common factor.

Code : (in JAVA)

 Sample input and output
1.Input
   8 5
  Output
   1
2.Input 
   26 4
  Output
   2

Please let me know if you have any questions .