Algorithm to select nodes and their parents in a tree

Let's say you have a tree structure as follows:

     a         [Level 0]
   / | \
  b  c  d      [Level 1]
 / \    |
e  f    g      [Level 2]
   |   / \
   h   i  j    [Level 3]

I have represented this in a database like so:

node  parent
------------
a     null
b     a
c     a
d     a
[...]
h     f
i     g     

I'd like to write a function that, given a level, it will return all nodes at that level and their parents.

For example:

f(0) => { a }
f(1) => { a, b,开发者_JS百科 c, d }
f(2) => { a, b, c, d, e, f, g }

Any thoughts?

---

Here I iterate through the levels, adding each one to the table with the level it is on.

create table mytable (
    node varchar(80),
    parent varchar(80),
    constraint PK_mytable primary key nonclustered (node)
)

-- index for speed selecting on parent
create index IDX_mytable_parent on mytable (parent, node)

insert into mytable values ('a', null)
insert into mytable values ('b', 'a')
insert into mytable values ('c', 'a')
insert into mytable values ('d', 'a')
insert into mytable values ('e', 'b')
insert into mytable values ('f', 'b')
insert into mytable values ('g', 'd')
insert into mytable values ('h', 'f')
insert into mytable values ('i', 'g')
insert into mytable values ('j', 'g')

create function fn_level (@level int) returns @nodes table (Node varchar(80), TreeLevel int)
as begin
    declare @current int
    set @current = 0
    while @current <= @level begin
        if (@current = 0)
            insert @nodes (Node, TreeLevel)
            select node, @current
            from mytable
            where parent is null
        else
            insert @nodes (Node, TreeLevel)
            select mt.node, @current
            from @nodes n
                inner join mytable mt on mt.parent = n.Node
            where n.TreeLevel = (@current - 1)
        set @current = @current + 1
    end
    return
end

select * from fn_level(2)

---

The usual way to do this, unless your flavour of SQL has a special non-standard function for it, is to build a path table that has these columns:

• parent_key
• child_key
• path_length

To fill this table, you use a recursive or procedural loop to find all of the parents, grand-parents, great-grand-parents, etc for each item in your list of items. The recursion or looping needs to continue until you stop finding longer paths which return new pairs.

At the end, you'll have a list of records that tell you things like (a,b,1), (a,f,2), (a,h,3) etc. Then, to get everything that is at level x and above, you do a distinct select on all of the children with a path_length <= x (unioned with the root, unless you included a record of (null, root, 0) when you started your recursion/looping.

It would be nice if SQL were better at handling directed graphs (trees) but unfortunately you have to cheat it with extra tables like this.

---

A solution for MySQL is less than ideal.

Assuming that the maximum depth of the tree is known:

SELECT
  nvl(e.node, nvl(d.node, nvl(c.node, nvl(b.node, a.node)))) item
, nvl2(e.node, 5, nvl2(d.node, 4, nvl2(c.node, 3, nvl2(b.node, 2, 1)))) depth
FROM table t AS a
LEFT JOIN table t AS b ON (a.node = b.parent)
LEFT JOIN table t AS c ON (b.node = c.parent)
LEFT JOIN table t AS d ON (c.node = d.parent)
LEFT JOIN table t AS e ON (d.node = e.parent)
WHERE a.parent IS NULL

This will give you every node and it's depth. After that it's trivial to select every item that has depth less that X.

If the depth of the tree is not known, or is significantly large then the solution is iterative as another poster has said.

---

Shamelessly copying from Jason, I made a function-less solution which I tested with postgresql (which has functions - maybe it would have worked out of the box).

create table tree (
    node char(1),
    parent char(1)
);

insert into tree values ('a', null);
insert into tree values ('b', 'a');
insert into tree values ('c', 'a');
insert into tree values ('d', 'a');
insert into tree values ('e', 'b');
insert into tree values ('f', 'b');
insert into tree values ('g', 'd');
insert into tree values ('h', 'f');
insert into tree values ('i', 'g');
insert into tree values ('j', 'g');

ALTER TABLE tree ADD level int2;
--
--  node  parent  level
--  a  -  1
--  b  a  a.(level + 1)
--  c  a  a.(level + 1)
--  e  b  b.(level + 1)
-- root is a:
UPDATE tree SET level = 0 WHERE node = 'a';
-- every level else is parent + 1: 
UPDATE tree tout      -- outer
  SET level = (
    SELECT ti.level + 1
    FROM tree ti   -- inner
    WHERE tout.parent = ti.node
    AND ti.level IS NOT NULL)
  WHERE tout.level IS NULL;

The update statement is pure sql, and has to be repeated for every level, to fill the table up.

kram=# select * from tree; 
 node | parent | level 
------+--------+-------
 a    |        |     1
 b    | a      |     2
 c    | a      |     2
 d    | a      |     2
 e    | b      |     3
 f    | b      |     3
 g    | d      |     3
 h    | f      |     4
 i    | g      |     4
 j    | g      |     4
(10 Zeilen)

I started with 'level=1', not '0' for a, therefore the difference.

---

SQL doesn't always handle these recursive problems very well.

Some DBMS platforms allow you to use Common Table Expressions which are effectively queries that call themselves, allowing you to recurse through a data structure. There's no support for this in MySQL, so I'd recommend you use multiple queries constructed and managed by a script written in another language.

---

I do not know much about databases, or their terminology, but would it work if you performed a joint product of a table with itself N times in order to find all elements at level N?

In other words, perform a query in which you search for all entries that have parent A. That will return to you a list of all its children. Then, repeat the query to find the children of each of these children. Repeat this procedure until you find all children at level N.

In this way you would not have to pre-compute the depth of each item.