Find a minimal binary tree that satisfies lowest common ancestor constraints

Question

I want to find if there's a fast algorithm for the following:

Given a set of lowest common ancestor constraints, find the smallest (fewest number of nodes) strict binary tree that satisfies all of them. Here, "strict" means that each node has either 0 or 2 children. The leaf nodes are labelled and multiple leaves can have the same label if necessary.

The lowest common ancestor constraints take the following form:

$$LCA(a_\textit{parity}, b_\textit{parity}) : \textit{Parity}$$

For example, you may have the following:

$$LCA(b_{even}, a_{odd}) : Even$$ $$LCA(a_{odd}, c_{even}) : Odd$$ $$LCA(a_{even}, b_{even}) : Odd$$ $$LCA(c_{even}, a_{even}) : Even$$

The first constraint would mean that the tree must have a "b" leaf on an even layer and an "a" leaf on an odd layer where their lowest common ancestor is on an even layer. The second constraint would mean that the tree must have an "a" leaf on an odd layer and a "c" leaf on an even layer where their lowest common ancestor is on an odd layer etc. Note that the root of the tree is the 0th layer, and thus, is even.

There are multiple minimal trees that satisfy the above constraints simultaneously, but one of them is the following:

Solution

Back to my original question, suppose I'm given an arbitrary set of these LCA constraints, is there a fast algorithm that can find a minimal tree that satisfies all of them? I suspect that the decision version of this problem is NP-Complete, but I haven't been able to find a reduction. Any ideas?

Thanks!