Click here to Skip to main content
Click here to Skip to main content

Finding the Lowest Common Ancestor in a tree

, 23 Sep 2012
Rate this:
Please Sign up or sign in to vote.
How to find the Lowest Common Ancestor in a tree.

Background

There are quite a few code snippets out there on the internet that finds the Lowest Common Ancestor. But all that I've seen has the drawbacks that they can only use two values as input and are usually vendor specific. I wanted the code to be a bit more general and to allow multiple inputs.

Using the code

This SQL script is easy enough to adjust to your needs, such as converting it to a stored procedure or a function.

The first CTE nodes is just a place holder for the indata in this demo code, and is supposed to be exchanged for your indata.

The second CTE called cte is a recursive CTE that's running the "wrong" direction and finds out all nodes above the input nodes and at the same time "marks" every row with the level in relation to the input nodes.

In the third CTE called levels we're finding out which tree IDs are existing as many times as the number of input nodes.

And then it's an easy thing to select the tree ID with the lowest level.

WITH nodes AS (
    SELECT treeid FROM tree WHERE treeid IN (14,27,32) --Exchange this for whatever input data you have
    )
,cte (treeid,lvl) AS (
    SELECT  treeid
           ,1
    FROM    nodes
    UNION all
    SELECT  parentid
           ,lvl + 1 lvl
    FROM    tree t,cte
    WHERE   t.treeid = cte.treeid
    )
,levels AS (
    SELECT  treeid
           ,Min(lvl) lvl
    FROM    cte
    HAVING  Count(lvl) = (SELECT Count(treeid) FROM nodes)
    GROUP BY treeid
    ORDER BY lvl
    )
,minlevel AS (
    SELECT  Min(lvl) minlevel
    FROM    levels
    )
SELECT  treeid
FROM    levels l,minlevel m
WHERE   l.lvl = m.minlevel

The slightly stupid construction in the last CTE have the purpose of making the construction compatible between SQL Server and Oracle. If you're using SQL Server you can easily exchange it for a TOP statement. And in Oracle ROWNUM = 1 (see below).

If you're using Oracle before 11G R2, you can't use recursive CTEs, instead you have to use the Connect By statement.

WITH nodes AS (
    SELECT treeid FROM tree WHERE treeid IN (14,27,32)
    )
,lvl AS (
    SELECT  treeid
           ,Min(LEVEL) lvl
    FROM    tree
    CONNECT BY PRIOR parentid = treeid
    START WITH treeid IN (SELECT treeid FROM nodes)
    HAVING Count(treeid) = (SELECT Count(*) cnt FROM nodes)
    GROUP BY treeid
    ORDER BY lvl
    )
SELECT  treeid
FROM    lvl
WHERE ROWNUM = 1

This construction is prettier, but also quite a bit slower than the recursive CTE when using large tables, because recursive CTEs are set based and connect by is a RBAR.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Jörgen Andersson
Database Developer
Sweden Sweden
No Biography provided

Comments and Discussions

 
-- There are no messages in this forum --
| Advertise | Privacy | Mobile
Web03 | 2.8.140827.1 | Last Updated 24 Sep 2012
Article Copyright 2012 by Jörgen Andersson
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid