CareerCup

LCA(root,a,b)
{
	if(a==root || b==root) return root;
	if(a->data < root->data && b->data < root->data)
		return LCA(root->left,a,b);
	if(a->data > root->data && b->data > root->data)
		return LCA(root->right,a,b);
	return root;
}

CountHops(root,a,b)
{
	if(!root || !a || !b) return INT_MIN;
	temp=LCA(root,a,b);
	hopa=-1;hopb=-1;
	p=temp;
	while(p!=a)
	{
		if(a->data < p->data)
			p=p->left;
		else
			p=p->right;
		hopa++;
	}
	p=temp;
	while(p!=b)
	{
		if(b->data < p->data)
			p=p->left;
		else
			p=p->right;
		hopb++;
	}
	return hopa + hopb + 1;	
}

Find the node at which a and b are split into right and left sub trees.Find the depth of that node.Find the depth of a and b.
Ans : depth(a)+depth(b)-2 depth(node at which a and b split)

Find the lowest common ancestor for the two given numbers. After that count the number of nodes between lowest common ancestor node & a and lowest common ancestor node & b.

answer = number of nodes to reach a+ number of nodes to reach b + 2

Eg.

Suppose the tree is as given below. a= 8. b= 26.

6
          /          \
        5             10
     /           /        \
   3             7        13
   \            \       /     \
    4            8      12     26

The lowest common ancestor would be:10

number of nodes to reach a=8 : 1
number of nodes to reach b=26 : 1

answer = 1+1 +2 = 4

// tree.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include "stdlib.h"
#include "stdio.h"
#include "string.h"


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

struct node *root;

void insert(struct node **root,int data)
{
if((*root)==NULL)
{
(*root)=(struct node *)malloc(sizeof(struct node));
(*root)->data =data;
(*root)->left =NULL;
(*root)->right =NULL;
}
else
{
if(((*root)->data) > data)
insert(&((*root)->left),data);
else
insert(&((*root)->right),data);
}
}

struct node * anc(struct node *root,int a,int b)
{
if((a==(root->data)) || (b==(root->data))) return root;
if((a < (root->data)) && (b < (root->data)))
return anc(root->left,a,b);
if((a > (root->data)) && (b > (root->data)))
return anc(root->right,a,b);
return root;
}

int hops(struct node *root,int a ,int b)
{
int count=0;
struct node*temp=NULL,*temp1=NULL;
temp=anc(root,a,b);
temp1=temp;
while(temp->data!=a)
{
if(temp->data >a)
temp=temp->left;
else
temp=temp->right;

count++;
}

while(temp1->data!=b)
{
if(temp1->data >b)
temp1=temp1->left;
else
temp1=temp1->right;

count++;
}
return count;
}

int main()
{
root=NULL;

int arr[10]={4,5,6,7,8,1,2,3,9,10};
int i=0;
struct node *temp=NULL;
while(i<10)
{
insert(&root,arr[i]);
i++;
}
temp=anc(root,7,10);

printf("%d",temp->data);


printf("\nhops==%d",hops(root,4,10));

return 1;
}

Assumption is that both the nodes/keys are present in the tree, the basic idea is same that we are trying to find the node from where split occurs and then we calculate the depth of the two nodes.

int find_depth(struct node* root, int val)
{
   if(!root) return 0;
   if(root->data == val) return 0;
   if(root->data < val)
      return 1+find_depth(root->left, val);
	else return 1+find_depth(root->right, val);
}

int find_hops_bst(struct node* root, int a, int b)
{
	if(!root) return 0;
	
	if(root->data == a)
	   return find_depth(root, b);
	
	if(root->data == b)
		return find_depth(root, a);
		
	//nodes on opposite side of the current root
	if( (root->data > a && root->data < b) ||  (root->data > b && root->data < a) )
	  return find_depth(root, a) + find_depth(root, b)-1;
	else{
		if (root->data > a)
			return find_hops_bst(root->left, a , b);
		else   
			return find_hops_bst(root->right, a , b);
	}
}

void hopcount(int element1,int element2,struct tree *root)
{
if((element1<root element && element2<root->element )|| (element1>root->element && element2>root->element))
printf("Hop Count=%d",abs(height(element1,root)-height(element2,root)));
else
printf("Hop count=%d",height(element1,root)+height(element2,root));
}

int height(int element,struct tree* root)
{
static int h=0;
if(root->ele==element)
return c;
else if(root->ele>element)
h=height(element,root->lchild,c+1);
else
h=height(element,root->rchild,c+1);
return h;
}

void hopcount(int element1,int element2,struct tree *root)
{
if((element1<root element && element2<root->element )|| (element1>root->element && element2>root->element))
printf("Hop Count=%d",abs(height(element1,root)-height(element2,root)));
else
printf("Hop count=%d",height(element1,root)+height(element2,root));
}


int height(int element,struct tree* root)
{
static int h=0;
if(root->ele==element)
return c;
else if(root->ele>element)
h=height(element,root->lchild,c+1);
else
h=height(element,root->rchild,c+1);
return h;
}