Complex TSQL order by clause

Question

Is it possible to craft an ORDER BY clause to ensure the following criteria for two fields (both of type INT), called child and parent respectively for this example.

1. parent references child, but can be null.
2. A parent can have multiple children; a child only one parent.
3. A child cannot be a parent of itself.
4. There must exist at least one child without a parent.
5. Each value of child must appear before it appears in parent in the ordered result set.

I'm having difficulty with point 5.

Sample unordered data:

child parent
------------
1     NULL
3     5
4     2
2     5
5     NULL

Obviously neither ORDER BY a, b or ORDER BY b, a work. In fact the more I think about it, I'm not sure it can even be done at all. Given the restrictions, obvious cases such as:

child parent
------------
1     2
2     1

aren't allowed because it violates rule 3 and 4 (and obviously 5).

So, is what I am trying to achieve possible, and if so how? Platform is SQL Server 2005.

Update: Desired sort order for the sample data:

child parent
------------
1     NULL
5     NULL
2     5
3     5
4     2

For each row that defines a non-null value in the parent column, the value has already been present int the child column.

Answer 1

You could use a recursive CTE to find the "depth" of each node, and order by that:

create table node (id int, parent int)
insert into node values (1, null)
insert into node values (2, 5)
insert into node values (3, 5)
insert into node values (4, 2)
insert into node values (5, null)
insert into node values (6, 4);

with node_cte (id, depth) as (
    select id, 0 from node where parent is null
    union all 
    select node.id, node_cte.depth + 1
    from node join node_cte on node.parent = node_cte.id    
) 

select node.* 
from node
join node_cte on node_cte.id=node.id
order by node_cte.depth asc

Answer 2

You won't be able to do it with an 'ORDER BY' clause because requirement 5 specifies that the order is sensitive to the data hierarchy. In SQL Server 2005 hierarchy data is usually dealt with using recursive CTEs; maybe someone here will provide appropriate code for this case.