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