1
$\begingroup$

I have the following interface:

public interface TreeElement<T>{
    public List<TreeElement<T>> getChildren();
}

Now, suppose I have a collection of TreeElement<T> representing a valid tree. How to find it's root element? Is there something more efficient than iterating over the whole collection?

$\endgroup$
12
  • 2
    $\begingroup$ Specific languages are off-topic here. Even more so anonymous programming languages. Could you explain the problem in more general terms than a specific program fragment. I have no idea how your syntax is to be read. If it is an algorithmic question, you should be able to specify abstractedly, and topossibly propose a solution in pseudo-code. $\endgroup$
    – babou
    Commented Jul 12, 2015 at 16:55
  • 1
    $\begingroup$ Iterating over the whole collection doing what? $\endgroup$
    – babou
    Commented Jul 12, 2015 at 17:01
  • 1
    $\begingroup$ @babou I think this question can be reasonably read as, "if I have a tree data structure in which nodes know their children (but not their parent), can I find the root in time $o(n)$"? $\endgroup$
    – Raphael
    Commented Jul 12, 2015 at 17:32
  • 1
    $\begingroup$ The question is underspecified. Are we only allowed to use this interface? If we control the implementation, we can just remember the root and get $O(1)$-time retrieval. $\endgroup$
    – Raphael
    Commented Jul 12, 2015 at 17:33
  • 1
    $\begingroup$ The question is asked as a (Java?) programming issue. A proper more language independent version would be something like: We have a TreeNode structure that is used to build tree. Assuming we have a set of such TreeNode's forming a single valid tree, that can be enumerated, and using only a getChildren fuction/method on the nodes, we want to determine which node is the root of the tree. Is there something more efficient than iterating over the whole set of TreeNode's? Prferably you should make precise what each iteration is supposed to be doing, if that is precise for you. CC @Raphael $\endgroup$
    – babou
    Commented Jul 13, 2015 at 11:29

1 Answer 1

4
$\begingroup$

I will make slightly stronger assumptions than that are provided in the question: we have a data structure, representing a tree, that consists of an array of vertices of the tree (allowing random access) and given a vertex, we have access to an array containing that vertex' children (again allowing random access). Furthermore we can check vertices for equality, and given a vertex we can (in $O(1)$ time) locate it in the main array.

On a tree of $n$ nodes, any strategy must take at least $\Omega(n)$ time in the worst case.

Consider a path of $n$ vertices. Define a vertex to be "examined" if it is accessed via the main array, via a children array or is reported as the root. Every non-leaf vertex must be examined by the algorithm: if some non-leaf vertex $v$ is not examined, we can make $v$ the root, making $v$'s child a child of $v$'s predecessor. This is not seen by the algorithm and it will incorrectly report the old root: making $v$ changes its children array (which is not seen by the algorithm as $v$ is not accessed at all) and changes the child array of $v$'s parent (which by the assumption of $v$ not being examined is not seen by the algorithm either).

Thus every non-leaf vertex in a path must be examined and any algorithm thus takes $\Omega(n)$ time.

$\endgroup$
6
  • $\begingroup$ I do not understand how examining solves a problem, unless you examine something specific in order to decide somethin. Neither the question nor the answer is very explicit about what is going on. $\endgroup$
    – babou
    Commented Jul 12, 2015 at 17:05
  • $\begingroup$ Unless you state precisely what you mean by "examining an element", I consider that you have no proof. $\endgroup$
    – babou
    Commented Jul 12, 2015 at 21:33
  • $\begingroup$ @babou I have clarified my proof and restated the question in my answer. $\endgroup$ Commented Jul 13, 2015 at 20:28
  • $\begingroup$ Nice rewriting (thanks), and good basis for discussion. I do not dispute your worst case asymptotic time. What I dispute is that you have to examine all vertices. Actually, when lucky, you could ignore more than half of them in the case of a complete binary tree. The point is that you have to know the total number of vertices, and for each node its number of children (you can do that without examining them). If at some point the number of unexamined children equals the number of remaining nodes, whatever is the current root candidate has to be the root: leafs are uninteresting. $\endgroup$
    – babou
    Commented Jul 13, 2015 at 22:48
  • $\begingroup$ @babou My claim that "every non-leaf vertex must be examined" only applies to the example of a path. In the best case you examine only $1$ vertex, namely when the tree consists of a single vertex with $n-1$ children. $\endgroup$ Commented Jul 14, 2015 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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