Find Lowest Common Ancestor in a Nested Set

I am looking for a way to find the Lowest Common Ancestor within a Nested Set can be found using a single equation.

For example, from the image at: https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

The LCA between Suits and Women's is Clothing. I could use a level based system to figure out where the parent's meet, but the use case for this is in database design therefore stepping up levels would be detrimental to performance.

I am hoping that I can use a single calculation using Suits (3:8) and Women's (10:21) to arrive at the combination (1:22) for clothing, that is if such an equation exists.

Nested sets have an interesting property that we can use to find all common ancestors. The property is simply that all children of a node have a left that is greater than its left AND a right that is less that its right.

This means that we need to find the nodes that have a left right bound that contains ALL of the nodes we care about. We can do this by using our set of nodes that we care about to set the bounds we are looking for. We can do this fairly easily as follows:

Take the lowest left and a highest right of all the nodes for which you want a common ancestor. In this case, the lowest left of your chosen nodes is 3 on suits and your highest right is 21 on Women's. You can then perform an ancestry query on this unified node-space of 3:21.

In this case you'd look for a set of nodes where left < 3 and right > 21. That would give you the set of all common ancestors. In this case the only match is clothing. The 1 on clothing is less than 3 and the 22 is greater than 21.

If you have multiple common ancestors but you want the lowest you can sort them by the left column in descending order and take the first one.

This might look something like this in SQL. I'm using T-SQL so the "top 1" might be limit 1 or something else in your flavor of SQL.

select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc