Shortest path in BST

Given a Binary Search Tree and two elements $$e1$$ and $$e2$$ which are in the tree, find the length of the shorted path between them. Give the representation of the Binary Search Tree(use a linked representation with dynamic allocation without an attribute for parent or height). Implement the required operation and specify its complexity. Hint: try to find first the Least Common Ancestor of the nodes, the first node which is an ancestor for both nodes.

I thought that for finding the Least Common Ancestor we have to make a preorder traversal for example having the while loop : $$while(!(e_1, but I don't know how to count the length between them. How should I count them?

– D.W.
Jun 12 '20 at 17:41
• What's your question? This is a question-and-answer site, so we require you to articulate a specific question about your situation. A question usually ends with a "?". Please ask only one question per post. I see several tasks in your problem statement. Note that we're not really looking for questions that are a statement of an exercise-style task and a request for us to solve it for you.
– D.W.
Jun 12 '20 at 17:42
• I don't know the source, but I know a harder version of this problem here timus.online/problem.aspx?space=1&num=1471&locale=en Jun 13 '20 at 4:48

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))$$.