Constructing Tree (forest) from Ancestor function
Assumptions

We have a finite set $\mathscr{D}$ of persons and a relation $\prec$: $x \prec y$ means that $x$ is an ancestor of $y$. This relation has the following properties:


Transitivity: if $x \prec y$ and $y \prec z$ then $x \prec z$ (the ancestor of my ancestor is my ancestor).
Antisymmetry: if $x \prec y$ then $y \nprec x$ (I am not my ancestor's ancestor).
Chain: if $x \prec z$ and $y \prec z$ then either $x \prec y$ or $x = y$ or $y \prec x$ (my ancestors form an ordered chain).


Data structures

Let it be given a set data structure on which the following operations are defined:


empty set
add an element to a set
splitting a set according to a property: iterate over the elements, compute a property on each element, and build two subsets, the set of elements for which the property is true and the set for which the property is false. This operation is assumed to be linear in the size of the set.


We will also use a tree data structure, in which each node contains a person and the set of its children. If $t$ is a tree, write $t_R$ for the person at the root node and $t_C$ for the set of children. A forest is a set of trees.

Algorithm

We start with an empty forest and add persons one by one. At each step, the parent-child relationship in the forest is the parent-child relationship for the ancestor relation. We define a recursive function graft that inserts a tree into a forest.

Input of graft: a forest $F$, and a tree $s$ such that none of the elements of the tree is related to any of the persons in $F$. Let $x = s_R$.

First, check whether $x$ is the ancestor of any of the existing persons: split the set $F$ according to the property $x \prec t_R$ for $t \in F$. Let $C$ be the subset of $F$ consisting of descendants of $x$ (if the root of a tree is a descendant of $x$ then all elements are also descendants by transitivity), and $F'$ be the remaining subset. By antisymmetry, none of the persons in $C$ is an ancestor of $x$. None of the elements of $s_C$ are related to any of the persons in $C$ by assumption. Let $u$ be the tree where the root person is $x$ and the set of children of the root is $C \cup s_C$.

By the chain assumption, $x$ can have ancestors in at most one of the trees in $F'$. Iterate over the trees $t \in F'$, and determine which one if any has an ancestor of $x$ at its root (this is a splitting operation where one of the sets is guaranteed to contain at most one element).

Output of graft:


If no tree in $F'$ has an ancestor of $F'$ at the root, then add the new node to the remaining forest: return $F' \cup \{u\}$.
If there is a tree $t$ in $F'$ such that $t_R \prec s$, then we need to insert the new element with its descendants into that tree. Let $G = \text{graft}(t_C, u)$. Return $(F' \setminus \{t\}) \cup \{t'\}$ where $t'$ has $t_R$ at the root and $G$ for children.


Main algorithm: Start from an empty forest, and iteratively graft the persons in $\mathscr{D}$ (grafting a person means grafting the tree with this person at the root and no children).

Correctness

From the remarks of this algorithm, it should be easy to prove that the recursive calls to graft are valid (all relatives of the nodes in the tree being inserted are inside that tree), and that $x$ is an ancestor of $y$ in the tree iff $x \prec y$.

Complexity

$\textrm{graft}(F,t)$ performs at most $2 n$ ancestor tests, where $n$ is the number of persons in $F$: one test per root of $F$, one test per root that is not a descendant of the new node, and tests performed by the recursive call if any which applies to a subset of $F$ not including any of its roots. The complexity of other operations is linear in the number of ancestor tests performed.

Therefore the forest construction algorithm performs at most $2 + 4 + 6 + \ldots + 2(n-1) = n (n-1)$ ancestor tests where $n$ is the total number of persons. In fact, it is easy to see that it never performs the same test twice. The overall complexity is therefore $O(n^2)$.

In the worst case, all possible $n (n-1)$ tests are performed. This happens when no two persons are related, and it is unavoidable in this case.