Shortest path in BST
There is a unique shortest path $P_T(u,v)$ between two nodes $u$ and $v$ in a tree $T$. Such a shortest path goes from $u$ to the lowest common ancestor (LCA) $z$ of $u$ and $v$ in $T$, and then goes from $z$ to $v$. Notice that it might be possible for $z$ to coincide with $u$ or $v$.

To find the length $d_T(u,v)$ of $P_T(u,v)$ is therefore sufficient to find the LCA $z$ of $u$ and $v$ in $T$.

There are several ways to do this. One straightforward way that requires time $O(n)$, where $n$ is the number of nodes of $T$, is the following:


Initially all the vertices of $T$ are unmarked.
Start from $u$ and iteratively walk towards the root of $T$. Mark all the encountered vertices.
Start from $v$ and iteratively walk towards the root of $T$. The LCA of $u$
and $v$ is the first marked vertex encountered during this walk.


An easy way to reduce the running time to $O(d_T(u,v))$ is that of alternating the steps of the walk from $u$ with those of the walk from $v$. Assume that $u \neq v$ (otherwise the answer is trivial) and do the following:


Initially all the vertices of $T$ are unmarked except for $u$ and $v$.
Let $p_u = u$, and $p_v = v$.
Repeat the following:


If $p_u$ is not the root of $T$:


Move $p_u$ to its parent in $T$.
If $p_u$ is marked, return $p_u$ as the LCA of $u$ and $v$. Otherwise mark $p_u$.

If $p_v$ is not the root of $T$:


Move $p_v$ to its parent in $T$.
If $p_v$ is marked, return $p_v$ as the LCA of $u$ and $v$. Otherwise mark $p_v$.




Once the LCA $z$ of $u$ and $v$ is known, it takes time $O(d_T(u,v))$ to find the distances from $z$ to $u$ and from $z$ to $v$ in $T$. Therefore $d_T(u,v)$ can be found in time $O(d_T(u,v)) = O(n)$.

If you have to frequently report the distance between pairs of vertices in a static tree then you can do so in constant time per query after a linear time preprocessing:


Build a LCA oracle: a data structure that can report the LCA between two vertces in $T$ in contant time. This data structure can be constructed in time $O(n)$. The construction is very clever and elegant. See this paper for the details.
Augment each node $v$ in the tree by storing its depth depth($v$) in $T$.
Answer a query for the distance between $u$ and $v$ in $T$ by: 1) finding the LCA of $z$ of $u$ and $v$ using the oracle; 2) returning $(\text{depth}(u) - \text{depth}(z)) + (\text{depth}(u) - \text{depth}(z))$.