### C++ program to find distance between two nodes of a binary search tree

#include <iostream>
#include <stdlib.h>
using namespace std;
/*
Description:
1.Create methods to implement binary search tree and insert elements
2.Start from the root node, if both keys are greater than current node,
we move to right child of current node. if both keys are smaller than
current node, we move to left child of current node.
3.If one keys is smaller and other key is greater, current node is Lowest
Common Ancestor (LCA) of two nodes. We find distances of current node
from two keys and return sum of the distances.

*/

class BinarySearchTree
{
public:
struct TreeNode
{
int key;
TreeNode* left;
TreeNode* right;
};
TreeNode* root;
public:
struct TreeNode *newNode(int item)
{
struct TreeNode *temp =  (struct TreeNode *)malloc(sizeof(struct TreeNode));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
struct TreeNode* insert(struct TreeNode* node, int key)
{
if (node == NULL)
return newNode(key);

if (key < node->key)
node->left  = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);

return node;
}
int distanceFromRoot(TreeNode* root, int x)
{
if (root->key == x)
{
return 0;
}else if (root->key > x)
{
return 1 + distanceFromRoot(root->left, x);
}
return 1 + distanceFromRoot(root->right, x);
}
int distanceBetween2(TreeNode* root, int a, int b)
{
if (!root)
{
return 0;
}
if (root->key > a && root->key > b)
{
return distanceBetween2(root->left, a, b);
}
if (root->key < a && root->key < b)
{
return distanceBetween2(root->right, a, b);
}
if (root->key >= a && root->key <= b)
{
return distanceFromRoot(root, a) + distanceFromRoot(root, b);
}
}
int findDist(TreeNode *root, int a, int b)
{
if (a > b)
{
swap(a, b);
}
return distanceBetween2(root, a, b);
}
};
int main()
{   int as=1;
do{
cout<<"1.CREATE A TREE.\n";
cout<<"2.FIND DISTANCE OF TWO NODE IN THE GIVEN TREE.\n";
cout<<"3.EXIT.\n";
int x;
int n,i=0,val;
BinarySearchTree t;
cin>>x;
//clrscr();
switch(x)
{
case 1:
cout<<"\nENTER THE NUMBER OF ELEMENTS YOU WANT TO INSERT:";
t.root = NULL;
cin>>n;
cout<<"\nENTER "<<n<<" ELEMENTS:";
while(i!=n)
{
cin>>val;
if(i==0)
{
t.root = t.insert(t.root,val);
}
t.insert(t.root,val);
i++;
}
break;
case 2:
int a,b;
cout<<"\nENTER THE ELEMENTS OF TWO NODES :\n";
cin>>a>>b;
cout<<"\nThe distance is : "<<t.findDist(t.root,a,b)<<endl;
break;
case 3:
as=0;
break;
}
}while(as);
return 0;
}
/*
OUTPUT :
1.CREATE A TREE.
2.FIND DISTANCE OF TWO NODE IN THE GIVEN TREE.
3.EXIT.
ENTER THE NUMBER OF ELEMENTS YOU WANT TO INSERT:6
ENTER 6 ELEMENTS:20 1 15 2 3 23
1.CREATE A TREE.
2.FIND DISTANCE OF TWO NODE IN THE GIVEN TREE.
3.EXIT.