# Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

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.

• I suggest you work through some examples until you spot the pattern.
– D.W.
Jan 23 at 17:06
• 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$? Jan 24 at 11:45
• @InuyashaYagami I assume that the overall number of vertices is a fixed large number.
– cory
Jan 24 at 13:31
• @cory I did not understand what you meant. By fixed, you mean $n = O(1)$? Jan 24 at 13:48

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

• I do not understand what you mean by $\{ min L, max L\}$. How it will give a minimal list? Thanks. Jan 24 at 17:20
• 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$. Jan 24 at 17:43
• Now, I understand your algorithm. Thanks for the explanation. Jan 24 at 18:12

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.