How to get root node in a tree

Question

Post reply

How to get root node in a tree

halifaxdal

SSCoach

Points: 19741
More actions
April 22, 2009 at 7:36 am

#136808

Hi folks,
I have a table, there are couple group in the table, for the nodes in each group, every node has a parent node, I need to find out the root node of each group, how should I write my query? Thanks.
Data sample:
ID Group Node Parent
1 1 aaa bbb
2 1 bbb ccc
3 1 ccc ddd
4 2 ddd eee
5 2 eee fff
6 2 fff ggg
7 3 ggg hhh
8 3 hhh iii
9 3 iii jjj
10 4 jjj kkk
11 4 kkk lll
12 4 lll mmm
....
You can see in the above data, root for each group are:
group root
1 ddd
2 ggg
3 jjj
4 mmm

Viewing 8 posts - 1 through 8 (of 8 total)

You must be logged in to reply to this topic. Login to reply

WayneS SSC Guru Points: 95461 More actions · Answer 1

-- build some test data... you should have provided this in this format for us

declare @temp table (

ID int,

[Group] int,

Node varchar(3),

Parent varchar(3))

insert into @temp

select 1,1,'aaa', 'bbb' union

select 2,1,'bbb', 'ccc' union

select 3,1,'ccc', 'ddd' union

select 4,2,'ddd', 'eee' union

select 5,2,'eee', 'fff' union

select 6,2,'fff', 'ggg' union

select 7,3,'ggg', 'hhh' union

select 8,3,'hhh', 'iii' union

select 9,3,'iii', 'jjj' union

select 10,4,'jjj', 'kkk' union

select 11,4,'kkk', 'lll' union

select 12,4,'lll', 'mmm'

-- here's what you're looking for

select [Group], MAX(Parent)

from @temp

group by [Group]

order by [Group]

Wayne
Microsoft Certified Master: SQL Server 2008
Author - SQL Server T-SQL Recipes

If you can't explain to another person how the code that you're copying from the internet works, then DON'T USE IT on a production system! After all, you will be the one supporting it!

Links:
For better assistance in answering your questions
Performance Problems
Common date/time routines
Understanding and Using APPLY Part 1 & Part 2

Mark Cowne One Orange Chip Points: 26983 More actions · Answer 2

select a.[Group],a.Parent as Root

from mytable a

where not exists (select * from mytable b where b.[Group]=a.[Group] and a.Parent=b.Node)

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

halifaxdal SSCoach Points: 19741 More actions · Answer 3

Neither of the code are working. :hehe:

1. to Wayne: what I gave in the sample data is really just an example, the order is not like that simple, I mean, not each group has its root with the biggest value

2. to Mark: your code will return multiple root for single group, and some group has wrong parent

Maybe this is not a task that can be accomplished by a single query? I wouldn't mind if a sp is required here.

Mark Cowne One Orange Chip Points: 26983 More actions · Answer 4

halifaxdal (4/22/2009)
Neither of the code are working. :hehe:
2. to Mark: your code will return multiple root for single group, and some group has wrong parent

Can you post some sample data

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

halifaxdal SSCoach Points: 19741 More actions · Answer 5

[/quote]

Can you post some sample data[/quote]

all right, here is a snap:

AAAPOS2122941POS2065860

BBBPOS2081642POS2081641

BBBPOS2084810POS2114958

BBBPOS2092572POS2081642

BBBPOS2089937POS2114958

BBBPOS1008747POS2081642

BBBPOS2114958POS2081641

BBBPOS2095265POS2081641

BBBPOS2078295POS2114958

BBBPOS0025394POS2081642

BBBPOS2092567POS2081641

BBBPOS2081641POS2122941

BBBPOS2092575POS2081642

BBBPOS2068844POS2081642

BBBPOS2119706POS2114958

CCCPOS2112258POS2122966

CCCPOS2112257POS2122966

CCCPOS2069283POS2057262

CCCPOS2045766POS2112257

CCCPOS2125450POS2069381

CCCPOS2057262POS2122966

CCCPOS2115660POS2112257

CCCPOS2121531POS2089901

CCCPOS2069381POS2057262

CCCPOS2115661POS2112257

CCCPOS2050452POS2122966

CCCPOS2122966POS2122961

CCCPOS2045536POS2112257

CCCPOS2095347POS2083347

CCCPOS2090072POS2112257

CCCPOS0025705POS2112258

CCCPOS2089901POS2112258

CCCPOS2027898POS2050452

CCCPOS2044542POS2050452

CCCPOS2048225POS2112257

CCCPOS2095281POS2083347

CCCPOS2089922POS2112257

CCCPOS2063877POS2050452

CCCPOS2111343POS2057262

CCCPOS2083465POS2083347

CCCPOS2083347POS2122966

CCCPOS2102437POS2057262

DDDPOS2093894POS2125992

DDDPOS2125992POS2122957

EEEPOS2107331POS2122941

EEEPOS2110913POS2107331

EEEPOS2112351POS2107331

FFFPOS2050455POS2122941

FFFPOS0024972POS2050455

FFFPOS2109848POS2050455

FFFPOS2008805POS2050455

Mark Cowne One Orange Chip Points: 26983 More actions · Answer 6

declare @mytable table (

[Group] varchar(30),

Node varchar(30),

Parent varchar(30))

insert into @mytable

SELECT 'AAA','POS2122941','POS2065860' UNION ALL

SELECT 'BBB','POS2081642','POS2081641' UNION ALL

SELECT 'BBB','POS2084810','POS2114958' UNION ALL

SELECT 'BBB','POS2092572','POS2081642' UNION ALL

SELECT 'BBB','POS2089937','POS2114958' UNION ALL

SELECT 'BBB','POS1008747','POS2081642' UNION ALL

SELECT 'BBB','POS2114958','POS2081641' UNION ALL

SELECT 'BBB','POS2095265','POS2081641' UNION ALL

SELECT 'BBB','POS2078295','POS2114958' UNION ALL

SELECT 'BBB','POS0025394','POS2081642' UNION ALL

SELECT 'BBB','POS2092567','POS2081641' UNION ALL

SELECT 'BBB','POS2081641','POS2122941' UNION ALL

SELECT 'BBB','POS2092575','POS2081642' UNION ALL

SELECT 'BBB','POS2068844','POS2081642' UNION ALL

SELECT 'BBB','POS2119706','POS2114958' UNION ALL

SELECT 'CCC','POS2112258','POS2122966' UNION ALL

SELECT 'CCC','POS2112257','POS2122966' UNION ALL

SELECT 'CCC','POS2069283','POS2057262' UNION ALL

SELECT 'CCC','POS2045766','POS2112257' UNION ALL

SELECT 'CCC','POS2125450','POS2069381' UNION ALL

SELECT 'CCC','POS2057262','POS2122966' UNION ALL

SELECT 'CCC','POS2115660','POS2112257' UNION ALL

SELECT 'CCC','POS2121531','POS2089901' UNION ALL

SELECT 'CCC','POS2069381','POS2057262' UNION ALL

SELECT 'CCC','POS2115661','POS2112257' UNION ALL

SELECT 'CCC','POS2050452','POS2122966' UNION ALL

SELECT 'CCC','POS2122966','POS2122961' UNION ALL

SELECT 'CCC','POS2045536','POS2112257' UNION ALL

SELECT 'CCC','POS2095347','POS2083347' UNION ALL

SELECT 'CCC','POS2090072','POS2112257' UNION ALL

SELECT 'CCC','POS0025705','POS2112258' UNION ALL

SELECT 'CCC','POS2089901','POS2112258' UNION ALL

SELECT 'CCC','POS2027898','POS2050452' UNION ALL

SELECT 'CCC','POS2044542','POS2050452' UNION ALL

SELECT 'CCC','POS2048225','POS2112257' UNION ALL

SELECT 'CCC','POS2095281','POS2083347' UNION ALL

SELECT 'CCC','POS2089922','POS2112257' UNION ALL

SELECT 'CCC','POS2063877','POS2050452' UNION ALL

SELECT 'CCC','POS2111343','POS2057262' UNION ALL

SELECT 'CCC','POS2083465','POS2083347' UNION ALL

SELECT 'CCC','POS2083347','POS2122966' UNION ALL

SELECT 'CCC','POS2102437','POS2057262' UNION ALL

SELECT 'DDD','POS2093894','POS2125992' UNION ALL

SELECT 'DDD','POS2125992','POS2122957' UNION ALL

SELECT 'EEE','POS2107331','POS2122941' UNION ALL

SELECT 'EEE','POS2110913','POS2107331' UNION ALL

SELECT 'EEE','POS2112351','POS2107331' UNION ALL

SELECT 'FFF','POS2050455','POS2122941' UNION ALL

SELECT 'FFF','POS0024972','POS2050455' UNION ALL

SELECT 'FFF','POS2109848','POS2050455' UNION ALL

SELECT 'FFF','POS2008805','POS2050455'

select a.[Group],a.Parent as Root

from @mytable a

where not exists (select * from @mytable b where b.[Group]=a.[Group] and a.Parent=b.Node)

What results are you expecting?

____________________________________________________

Deja View - The strange feeling that somewhere, sometime you've optimised this query before

How to get the best help on a forum

http://www.sqlservercentral.com/articles/Best+Practices/61537

halifaxdal SSCoach Points: 19741 More actions · Answer 7

All right, I found the reason why the result seems wrong, sorry Mark, the original data is not well normalized, your code is good. 😉