# algorithms – Finding largest disjoint subtrees spanning nodes

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?