1
$\begingroup$

The input: a binary tree and a list $L$ of vertices in that tree.

The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of minimal length it is OK to output any one of them.

We could just check all the possible sublists of $L$ but that seems inefficient.

Is there an algorithm for this problem whose running time grows polynomially with respect to the length of $L$?

One idea that doesn't work is checking for each vertex in $L$ whether removing it changes the lowest common ancestor and then simply removing the "useless" vertices. If it worked the running time would be linear.

Another idea that might work but I haven't verified in detail is to pick one vertex removing which doesn't change the lowest common ancestor, then remove it and again pick one vertex etc. This has a quadratic time.

$\endgroup$
4
  • $\begingroup$ I suggest you work through some examples until you spot the pattern. $\endgroup$
    – D.W.
    Jan 23 at 17:06
  • $\begingroup$ Designing an algorithm that is bounded by $poly(|L|)$ might not be possible since finding the lowest common ancestor just for two nodes would take $\Omega(n)$ time and $n$ could be exponential in $(|L|)$. Are you sure you are looking for a $poly(|L|)$ algorithm and not for some linear/quadratic algorithm in $n$? $\endgroup$ Jan 24 at 11:45
  • $\begingroup$ @InuyashaYagami I assume that the overall number of vertices is a fixed large number. $\endgroup$
    – cory
    Jan 24 at 13:31
  • $\begingroup$ @cory I did not understand what you meant. By fixed, you mean $n = O(1)$? $\endgroup$ Jan 24 at 13:48
1
$\begingroup$

Consider your binary tree as a binary search tree on the integers $1$ through $n$ to find that the answer for some given list $L \subseteq [1, n]$ will be $\{\min L, \max L\}$. In case you are not given a BST, you can traverse the given tree in-order to find those values in linear time (though that might be dependent on the data structure used to store $L$).

$\endgroup$
3
  • $\begingroup$ I do not understand what you mean by $\{ min L, max L\}$. How it will give a minimal list? Thanks. $\endgroup$ Jan 24 at 17:20
  • $\begingroup$ By that I mean the minimal and maximal elements of $L$ according to an in-order traversal of the given tree, respectively. They are basically the "leftmost" and "rightmost" nodes in $L$. $\endgroup$ Jan 24 at 17:43
  • $\begingroup$ Now, I understand your algorithm. Thanks for the explanation. $\endgroup$ Jan 24 at 18:12
0
$\begingroup$

Suppose $v$ is the lowest common ancestor of the given list of vertices $L$. Let $T_{\ell}$ denote the subtree rooted at the left child of $v$, and $T_{r}$ denote the subtree rooted at the right child of $v$.

Observation: There are two vertices $x$ and $y$ in $L$ such that $x$ belongs to $T_{\ell}$ and $y$ belongs to $T_{r}$.

Proof: For the sake of contradiction assume that the above fact is not true. Now, without loss of generality, we can assume that there is no vertex in $L$ that belongs to $T_{r}$. In this case, the left child of $v$ can act as an ancestor of $L$. Moreover, it appears in the tree at a lower level than $v$. This contradicts that $v$ is the lowest common ancestor of $L$.

Based on the above observation, we can further say that $v$ is the lowest common ancestor of $x$ and $y$. Because if this is not the case, $x$ and $y$ would have appeared in the same subtree $T_{\ell}$ or $T_{r}$.

Now, your algorithm just needs to output these two vertices $x$ and $y$ since these vertices are the minimal vertices that have the same ancestor as $L$. This gives the following linear time algorithm for the problem.

Algorithm:

  1. Find the lowest common ancestor of $L$ in $O(n)$ time. Suppose $v$ is this ancestor.

  2. If $v \in L$, output $v$.

  3. If $v \notin L$, perform a DFS in $T_{\ell}$ and $T_{r}$. Find any vertex $x \in T_{\ell}$ that belongs to $L$, and any vertex $y \in T_{r}$ that belongs to $L$. Output $x$ and $y$. This step takes $O(n)$ time.

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