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);

}

}