//https://www.geeksforgeeks.org/find-distance-between-two-nodes-of-a-binary-tree/
#include <iostream>
using namespace std;
struct node {
int data;
node *left, *right;
};
node *newNode (int n) {
node *temp= (node*)malloc(sizeof(node));
temp->data= n;
temp->left= temp->right= NULL;
return temp;
}
node *findDist (node *root, int n1, int n2, int &d1, int &d2, int &dist, int level) {
if (root== NULL)
return NULL;
if (root->data== n1) {
d1= level;
return root;
}
if (root->data== n2) {
d2= level;
return root;
}
node *Tleft= findDist(root->left, n1,n2,d1,d2,dist, level+1);
node *Tright= findDist(root->right, n1,n2,d1,d2,dist, level+1);
if (Tleft && Tright) {
dist= d1+d2- 2*level;
return root;
}
return (Tleft)?Tleft:Tright;
}
int findLevel (node *root, int n, int level) {//here level is the height of the the node from root.
if (root== NULL)
return -1;
if (root->data== n)
return level;
int k= findLevel(root->left, n, level+1);
return (k== -1)?findLevel(root->right, n, level+1):k;
}
int findDistance (node *root, int n1, int n2) {
int d1= -1, d2=-1 ,dist;
node* lca = findDist(root, n1, n2, d1,d2,dist,1);
if (d1 != -1 && d2!= -1)
return dist;
if (d1== -1) {
dist= findLevel (lca, n1, 0);
return dist;
}
if (d2== -1) {
dist= findLevel (lca, n2, 0);
return dist;
}
return -1;
}
int main() {
node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
root->right->left->right = newNode(8);
cout << "Dist(4, 5) = " << findDistance(root, 4, 5)<< endl;
cout << "nDist(4, 6) = " << findDistance(root, 4, 6)<< endl;
cout << "nDist(3, 4) = " << findDistance(root, 3, 4)<< endl;
cout << "nDist(2, 4) = " << findDistance(root, 2, 4)<< endl;
cout << "nDist(8, 5) = " << findDistance(root, 8, 5)<< endl;
return 0;
}