Algorithm to select nodes and their parents in a tree

Question

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, c, d }
f(2) => { a, b, c, d, e, f, g }

Any thoughts?

Answer 1

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)

Answer 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.