CareerCup

Probably find lca of n1 and n2. Now, find the path length from lca from n1 and n2 and sum it.

I guess by distance you mean "length of the path from n1 to n2"...

so the idea is to do a special case on the diameter of the tree rooted at the given root, but only till nodes n1 and n2...

see here for more: geeksforgeeks.org/archives/5687

1 way which comes in top of my head

a) find LCA
b) find the distance of node 1 and node 2 from LCA. Sum it up.

Assuming a binary tree, the solution should look like the following:
1. find the difference between the heights of the two nodes. (diff)
2. depending upon the difference in height, change the pointer to the node, such that, both the pointers are at the same depth.
3. While the pointers do not point at the same node, keep assigning the pointer to the parent of the current node. Also, keep counting the steps (d_factor).
4. Total Distance = ( 2 * d_factor) + diff

Here's the code snippet:
----
d1 = depthOf(n1);
d2 = depthOf(n2);
diff = d1 - d2;
if ( d1 > d2 )
{
for ( int i = 0 ; i < diff; i++ )
n1 = n1->parent;
}
else
{
for ( int i = 0 ; i < diff; i++ )
n2 = n2->parent;
}

dist_factor = 0;
while ( node1 != node2 )
{
node1 = node1->parent;
node2 = node2->parent;
dist_factor++;
}

totalDistance = (2 * dist_factor) + diff;
--

Even when the tree is not BST we can find LCA by writting the inorder and pre-order traversal of the tree and then finding the first node in pre-order for which n1 and n2 are on different side.

then sum of distance for LCA to n1 and n2 is the ans

dist(n1,n2)= dist(root,n1)+ dist(root,n2) - 2* LCA(n1,n2)

1) Do an INorder traversal, store it in an array
2) count the elements between the n1 and n2.
3) Return the counter or print the elements