Depth Travesal
 

Hi, I am a newbie for MSSQL. Previously, I was given a question regarding MSSQL. Although the interview had over, but I am curious to find out on how to solve the question below:

There are 2 tables, NAMES (ID INT IDENTITY(1,1), NAME SYSNAME) and
RELATIONSHIPS (NAMEID INT, PARENT_NAMEID INT) linked via NAMES.ID=
RELANTIONSHIP.NAMEID and where top-most name has a PARENT_NAMEID=0.
Show a nested list of names including LEVEL, NAMEID and NAME, where
LEVEL indicates the nest level (or depth) from top. You may use functions,
stored procedures,views and any other Transact SQL commands compliant
with Microsoft SQL 2000.


Sample Data:
NAMES table content
ID NAME
1 Frank
2 Jo
3 Mary
4 Peter
5 Amy


RELATIONSHIPS table content

NAMEID PARENT_NAMEID
1 0
2 1
3 2
4 1
5 2


Expected Output

LEVEL ID NAME
0 1 Frank
1 2 Jo
2 5 Amy
2 3 Mary
1 4 Peter

Thanks in advanced

Re: Depth Travesal
 

Try this code in Query Analyser. It enough for small data. If you want to use for big data, modify the code.

set nocount on

create table #tmpName (ID int, [Name] varchar(255))

create table #tmpRelation (ID int, ID_Parent int)



insert #tmpName (ID, [Name]) select 1, 'Frank'

insert #tmpName (ID, [Name]) select 2, 'Jo'

insert #tmpName (ID, [Name]) select 3, 'Mary'

insert #tmpName (ID, [Name]) select 4, 'Peter'

insert #tmpName (ID, [Name]) select 5, 'Amy'



insert #tmpRelation (ID, ID_Parent) select 1, 0

insert #tmpRelation (ID, ID_Parent) select 2, 1

insert #tmpRelation (ID, ID_Parent) select 3, 2

insert #tmpRelation (ID, ID_Parent) select 4, 1

insert #tmpRelation (ID, ID_Parent) select 5, 2



create table #tmpResult (ID int, ID_Parent int, [Level] int, [Name] varchar(255))



insert #tmpResult (ID, ID_Parent, [Level], [Name])

  select N.ID, R.ID_Parent, 0, N.[Name]

    from #tmpName N inner join #tmpRelation R on

        N.ID = R.ID

    where ID_Parent = 0



while exists (select 1 from #tmpName N left join #tmpResult R on N.ID = R.ID where R.ID is null)

begin

  insert #tmpResult (ID, ID_Parent, [Level], [Name])

    select N.ID, R.ID_Parent, C.[Level] + 1, N.[Name]

      from #tmpName N inner join #tmpRelation R on

        N.ID = R.ID inner join (

                        select        P.ID, P.[Level]

                          from        #tmpResult P left join #tmpResult C on

                                P.ID = C.ID_Parent

                          where C.ID is null

                                ) C on

        R.ID_Parent = C.ID

end



select ID, [Level], Name from #tmpResult



drop table #tmpResult

drop table #tmpName

drop table #tmpRelation

Re: Depth Travesal
 

Thanks Huangzi, will test it later. Thanks again for the solution you offer.