Finding largest disjoint subtrees spanning nodes

Question

I have a taxonomy (tree) of product categories. To each leaf product category, I have assigned a shop department where the products of a given category can be found.

Now for each department, I would like to find the smallest number of the largest subtrees in the taxonomy.

For instance, in the example below leaf nodes have been assigned one of two departments $A$ and $B$.

The expected solution would be: $A$ has two subtrees, namely $x_2$ and $x_7$, $B$ has one subtree $x_4$.

The solution where $A$ has $x_1$ subtree is wrong because $x_1$ is the ancestor of nodes that belong to another department.

The solution where $A$ has $x_3$ and $x_7$ subtrees is wrong because we want the biggest subtrees possible.

Is it a known problem?

Is there a solution for it?

Answer 1

Here's an algorithm. Let $D(l)$ denote the department of the product category of a leaf $l$.

To find the subtree for leaf $l$ do the following. For every leaf $l'$ such taht $D(l') \neq D(l)$, mark the node $\text{lca}(l, l')$. Now, your largest subtree is the subtree rooted in the highest unmarked node. Call this node $\text{root}(l)$.

To compute for all leaves, clear the marks and output $\bigcup_{l \in L} \text{root}(l)$, where $L$ is the set of leaves.

---

A different (faster) algorithm: For each leaf $l$, move upwards and mark each node with $D(l)$. If you hit a node already marked $D(l)$, you move on to the next leaf. If you hit a node marked with a different color, delete the node. Then your connected components should be your largest disjoint subtrees.

---

You ask if it's a known problem, I think that the closest you get to a known problem is the lowest common ancestor problem.