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 &quot;useless&quot; 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.
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$).