0
$\begingroup$

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<a == e_2 < a))$, but I don't know how to count the length between them. How should I count them?

$\endgroup$
3
  • 1
    $\begingroup$ Please credit the source where you encountered this task. $\endgroup$
    – D.W.
    Jun 12 '20 at 17:41
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Jun 12 '20 at 17:42
  • $\begingroup$ 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 $\endgroup$
    – IS3NY
    Jun 13 '20 at 4:48
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.