One naïve idea can be searching for either of the nodes using BFS. Once either of the nodes is found, corresponding node is marked. We start searching for the other node incrementing distance. But one problem is result always is not guaranteed to be minimum.

Rather what actually should come to your mind is what can be closest node for both the target nodes (distance between those nodes that are to be found). The answer will be lowest common ancestor. So, we actually need to find the lowest common ancestor of two target nodes. Then, we can think the LCA to be root and the target nodes exist in two different branches. (Example 1)

Or there can be situation that both the target nodes exists on same root to leaf path that means one of the two target nodes itself is LCA. (Example 2)

However rest of our job is two find distance of respective target nodes from the LCA.

Let the distances to be distance1 and distance2 respectively.

Then the minimum distance between the two target nodes will be = distance1+distance2

How to find LCA?

Can be done using preorder traversal.

Pre-requisite:

Tree root, target node data values a, b

FUNCTION LCA (root, a, b)
//base case
IF(!root)
return NULL;
IF(root->data==a || root->data==b) //it ensures to root to be LCA
return root;
Node* l=findlowestancestor(root->left,a,b);
Node* r=findlowestancestor(root->right,a,b);
if(l && r) //this can only happen incase of LCA be root
return root;
return (l==NULL ?r:l); //NOT NULL one between l and r which contains LCA node
END FUNCTION

After finding the LCA we compute the distance separately for two nodes. This can be done by level order traversal finding number of levels between target node and root (LCA).

Example with explanation:

Example 1:

Target nodes:
9 and 2
LCA:
Node with value 5
Distance1: //distance between 5 and 9
1
Distance2: //distance between 5 and 2
2
Their min distance is 1+2=3

Example 2:

Target nodes:
4 and 3
LCA:
Node with value 4 (first target node itself)
Distance1: //distance between 4 and 4
0
Distance2: //distance between 4 and 3
2
Their min distance is 0+2=2

C++ implementation:

#include <bits/stdc++.h>
using namespace std;
class Node{ //tree node
public:
int data;
Node *left;
Node *right;
};
//finding lowest common ancestor
Node* findlowestancestor(Node* root,int a,int b){
if(!root)
return NULL;
if(root->data==a || root->data==b)
return root;
Node* l=findlowestancestor(root->left,a,b);
Node* r=findlowestancestor(root->right,a,b);
if(l && r)
return root;
return (l==NULL ?r:l);
}
//finding distance between root(LCA) and target node
int height(Node* root, int a){
//base cases
if(root==NULL)
return 0;
if(root->data==a)
return 0;
//level order
queue<Node*> q;
q.push(root);
q.push(NULL);
int height=0;
while(!q.empty()){
Node* temp=q.front();
q.pop();
if(!temp){
if(!q.empty()){
q.push(NULL);
}
height++;
}
else{
if(temp->data==a)
return height;
if(temp->left)
q.push(temp->left);
if(temp->right)
q.push(temp->right);
}
}
return height;
}
int findDist(Node* root, int a, int b)
{
Node* t=findlowestancestor(root,a,b);
int p=height(t,a);
int q=height(t,b);
return p+q;
}
//creating new nodes
Node* newnode(int data){
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main() {
//**same tree is builted as shown in example**
cout<<"tree in the example is build here"<<endl;
//building the tree like as in the example
Node *root=newnode(8);
root->left= newnode(5);
root->right= newnode(4);
root->right->right=newnode(1);
root->right->right->left=newnode(3);
root->left->left=newnode(9);
root->left->right=newnode(7);
root->left->right->right=newnode(2);
cout<<"Example 1......"<<endl;
cout<<"Miniimum distance between 9 and 2\n";
cout<<findDist(root,9,2)<<endl;
cout<<"Example 2......"<<endl;
cout<<"Miniimum distance between 4 and 3\n";
cout<<findDist(root,4,3);
return 0;
}

Output

tree in the example is build here
Example 1......
Miniimum distance between 9 and 2
3
Example 2......
Miniimum distance between 4 and 3
2

One naïve idea can be searching for either of the nodes using BFS. Once either of the nodes is found, corresponding node is marked. We start searching for the other node incrementing distance. But one problem is result always is not guaranteed to be minimum.

Rather what actually should come to your mind is what can be closest node for both the target nodes (distance between those nodes that are to be found). The answer will be lowest common ancestor. So, we actually need to find the lowest common ancestor of two target nodes. Then, we can think the LCA to be root and the target nodes exist in two different branches.

(Example 1)Or there can be situation that both the target nodes exists on same root to leaf path that means one of the two target nodes itself is LCA.

(Example 2)However rest of our job is two find distance of respective target nodes from the LCA.

Let the distances to be

distance1anddistance2respectively.Then the minimum distance between the two target nodes will be

= distance1+distance2How to find LCA?Can be done using

traversal.preorderPre-requisite:Tree root, target node data values a, b

After finding the LCA we compute the distance separately for two nodes. This can be done by level order traversal finding number of levels between target node and root (LCA).

Example with explanation:Example 1:Example 2:C++ implementation:Output