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.

  • $\begingroup$ 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" $\endgroup$ – dzieciou Jan 17 at 12:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.