WAP find Minimum Distance Between two Nodes In Binary Tree

Algorithm

Assume each node has parent pointer:
let distance d=0;
1. Start from the node 1 and find the distance of the node from root by traversing up. let it be d1.
2. start from node 2 and do the same. let this distance be d2.
3.if(d1>d2) then traverse d1-d2 nodes up from the node2. add d=d+(d1-d2)
4.now traverse up from each node from that place until both point to same node. while traversing up make d=d+2;
5. when both reaches to same node, it represents the common ancestor. so substract 1 from d.
6. now d represents the distance between two nodes.

Algo Suggested By sreenivas putta then I Coded It.

Efficiency Level:- Not Efficient (cause Parent Pointer Overhead)

#include
#include

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
struct node* parent;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int distance(struct node* root, struct node* n1,struct node* n2)
{
int d=0,d1=0,d2=0;
struct node* temp=n1;

while(temp->parent!=NULL)
{
temp=temp->parent;
d1++;

}
temp=n2;

while(temp->parent!=NULL)
{
temp=temp->parent;
d2++;

}
if(d1>d2)
{

d=d1-d2;
while((d1-d2)>0)
{

n1=n1->parent;
d1--;
}

}
else
{
d=d2-d1;
while((d2-d1)>0)
{
n2=n2->parent;
d2--;
}

}
while(n1!=n2)
{

n1=n1->parent;
n2=n2->parent;
d+=2;

}
return d;

}

/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node)
{
if (node == NULL)
return;

/* first print data of node */
printf("%d ", node->data);

/* then recur on left sutree */
printPreorder(node->left);

/* now recur on right subtree */
printPreorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
struct node *root = newNode(1);
root->parent=NULL;

root->left = newNode(2);
root->right = newNode(3);
root->left->parent=root;
root->right->parent=root;

root->left->left = newNode(4);
root->left->right = newNode(5);
root->left->left->parent=root->left;
root->left->right->parent=root->left;

root->left->left->left = newNode(6);
root->left->left->right = newNode(7);
root->left->left->left->parent= root->left->left;
root->left->left->right->parent= root->left->left;

root->left->right->left = newNode(8);
root->left->right->right = newNode(9);
root->left->right->left->parent= root->left->right;
root->left->right->right->parent= root->left->right;

root->right->left = newNode(10);
root->right->right = newNode(11);
root->right->left->parent=root->right;
root->right->right->parent=root->right;


root->right->left->left = newNode(12);
root->right->left->right = newNode(13);
root->right->left->left->parent=root->right->left;
root->right->left->right->parent=root->right->left;

root->right->right->left = newNode(14);
root->right->right->right = newNode(15);
root->right->right->left->parent=root->right->right;
root->right->right->right->parent=root->right->right;

//printf("\n Preorder traversal of binary tree is \n");
//printPreorder(root);

printf( " %d ", distance(root, root->left->left->left , root->right->right->right));

getchar();
return 0;
}

TC O(n)
Sc O(1)
Run Here https://ideone.com/aFNsP