Given an arbitrarily ordered tree, how do I find the first and last element of an arbitrary set of its elements?

Question

I have a tree, constructed of TreeItems. Each TreeItem has these methods:

TreeItem   TreeItem::getParent()
TreeItem[] TreeItem::getChildren()
int        TreeItem::indexOf(TreeItem childItem)

I also have an unordered set of TreeItems from this tree. I want to quickly find the first element and the last element of this set.

Any clever ideas?

Answer 1

Select one of a tree items in your set (I'll assume given set is subtree), then first find the parent of this set:

while (element.getParent()!=null)
  element = element.getParent();
parent = element;

Now you have parent, and you just need iterate its children recursively:

TreeItem TreeItem::getLastChild()
{
 children = getChildren();
 if (children == null)
   return parent;

 int maxIndex = 0;

   // find child with maximum index
   .....

  return foundedChild.getLastChild();
}