Name for algorithm reconstructing tree from lowest common ancestor?

Question

I'd like to write a tool that works on some tree-structured data. (In fact it will work on a tree-like subset of a git revision DAG, but that's not important for this question). In particular I want an algorithm that reconstructs a subset of the tree consisting of all the "join points" of a given input set.

Specifically what I think I want is

• We have some type H that has a "lowest common ancestor" function, lca on it. This gives H a tree-like structure.

• The algorithm takes some subset S of H as input.

• The output should be a multi-way tree t with nodes labelled by values of H.

• t should satisfy the properties

  • All s in S label some node of t

  • The leaves of t can only be labelled by elements of S

  • Any element h for H labels no more than one node of t

  • If h1 labels n1 and h2 labels n2 then lca(h1, h2) labels the lowest common ancestor of n1 and n2 in t.

My question is: "Is this a known problem with known algorithms?". I suspect it is. It seems quite similar to a topological sort. I have an idea for an algorithm based on merge sort but if known algorithms already exist there's no reason to come up with my own.

Answer 1

I don't know what you call it, but I'd first compare all pairs of elements to construct the partial order for the tree, then do a topological sort, then construct the tree from that. (The point of sorting it is that now you know that the first element is the root, and each element in turn will be a leaf.)

The subject reminded me of cladistics algorithms, http://bio.slu.edu/mayden/systematics/bsc420520lect12.html. However those are both easier and harder. Easier because it is easy to tell upon inspection which forms are close to another. Harder because the challenge is that you don't know the LCA. So pursuing that might be an interesting side track but is probably not very helpful.