# 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?

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.

• Thank you for using the term color, it makes the problem (and solution) more universal, like "Finding largest disjoint subtrees spanning leaves of same color" Jan 17, 2021 at 12:36