Given two nodes of a Binary Tree, write a program to determine the shortest distance between the two nodes.

Approach:
1. Find the lowest common ancestor of the given nodes.
2. Find the distance (levels) between the lowest common ancestor and each given node separately.
3. Add the distances obtained in Step-2.

#include<iostream>
using namespace std;
struct node
{
 int data;
 struct node* left;
 struct node* right;
};
struct node* createnode(int x)
{
 struct node* new_node=new struct node;
 new_node->data=x;
 new_node->left=NULL;
 new_node->right=NULL;
 return new_node;
};
int help_anc(struct node* root,node* n1,node* n2)
{
    if(root)
    {
        if(root==n1)
        {
            return 1;
        }
        else if(root==n2)
        {
            return 1;
        }
        else
        {
            return help_anc(root->left,n1,n2)+help_anc(root->right,n1,n2);
        }
    }
    else
    {
        return 0;
    }
}
struct node* Ancestor(node* root,node* n1,node* n2)
{
    if(root)
    {
        int lf = help_anc(root->left,n1,n2);
        int rf = help_anc(root->right,n1,n2);
        if(lf==1 && rf==1)
        {
            return root;
        }
        else
        {
            node* lca = Ancestor(root->left,n1,n2);
            if(lca!=NULL)
            {
                return lca;
            }
            lca = Ancestor(root->right,n1,n2);
            return lca;
        }
    }
    else
    {
        return NULL;
    }
}

int customheight(node *root,node *n1,bool *found)
{
    int lheight=0,rheight=0;
    if(root)
    {
        if(*found==false && root==n1)
        {
            *found=true;
            return 0;
        }
        else if(*found==false)
        {
            lheight=customheight(root->left,n1,found);
            rheight=0;
            if(*found==false)
            {
                rheight=customheight(root->right,n1,found);
            }
            if(*found==true)
            {
                return lheight>rheight?1+lheight:1+rheight;
            }
            else
            {
                return 0;
            }
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return 0;
    }
}
int distancethroughlca(node* n1,node* n2,node* lca)
{
    if(lca)
    {
        bool found=false;
        int dist1=customheight(lca,n1,&found);
        cout<<"Distance of "<<n1->data<<": "<<dist1<<endl;
        found=false;
        int dist2=customheight(lca,n2,&found);
        cout<<"Distance of "<<n2->data<<": "<<dist2<<endl;
        return dist1+dist2;
    }
    else
    {
        return 0;
    }
}

int main()
{
    struct node* root=createnode(1);
 root->left=createnode(2);
 root->right=createnode(3);
 root->left->right=createnode(4);
 root->left->left=createnode(5);
 root->right->right=createnode(6);
 root->right->left=createnode(7);
 root->right->right->left=createnode(8);
 //root->right->right->left->left=createnode(10);
 root->right->right->right=createnode(10);
 struct node* n1 = root->right->right->left;
 struct node* n2 = root->right->right->right;
 struct node* lca=Ancestor(root,n1,n2);
 if(lca)
 {
     cout<<"Least Common Ancestor: "<<lca->data<<endl;
 }
 cout<<"Total distance through LCA: "<<distancethroughlca(n1,n2,lca)<<endl;
}
Output:
Least Common Ancestor: 1
Distance of 8: 3
Distance of 4: 2
Total distance through LCA: 5