WITH RECURSION output ordering with trees

Hi,

I'm playing with the new "WITH RECURSIVE" feature of 8.4. I'm trying to
figure out how to use it with trees.

Here is the test code I use:

---------------------------------------------------------
--DROP TABLE recursion;

CREATE TABLE recursion
(
id serial,
lookup varchar(16),
parent_id integer,
primary key(id),
foreign key(parent_id) references recursion(id)
);

INSERT INTO recursion VALUES(1, 'a1', NULL);
INSERT INTO recursion VALUES(2, 'b11', 1);
INSERT INTO recursion VALUES(645, 'c111', 2);
INSERT INTO recursion VALUES(823, 'c112', 2);
INSERT INTO recursion VALUES(243, 'c113', 2);
INSERT INTO recursion VALUES(6, 'b12', 1);
INSERT INTO recursion VALUES(845, 'c121', 6);
INSERT INTO recursion VALUES(583, 'c122', 6);
INSERT INTO recursion VALUES(9, 'b13', 1);
INSERT INTO recursion VALUES(10, 'c131', 9);

WITH RECURSIVE parse_tree (depth, id, lookup, parent_id) AS
(
SELECT
0,
parent.id,
parent.lookup,
parent.parent_id
FROM recursion AS parent
WHERE parent_id IS NULL

UNION ALL

SELECT
parent.depth + 1,
child.id,
child.lookup,
child.parent_id
FROM parse_tree parent, recursion AS child
WHERE child.parent_id = parent.id
)

SELECT * FROM parse_tree;
---------------------------------------------------------

Here is the result:

depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
1 | 6 | b12 | 1
1 | 9 | b13 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
2 | 845 | c121 | 6
2 | 583 | c122 | 6
2 | 10 | c131 | 9

I'd like to perform a real recursion, and show the tree structure in a
more appopriate way, like this:

depth | id | lookup | parent_id
-------+-----+--------+-----------
0 | 1 | a1 |
1 | 2 | b11 | 1
2 | 645 | c111 | 2
2 | 823 | c112 | 2
2 | 243 | c113 | 2
1 | 6 | b12 | 1
2 | 845 | c121 | 6
2 | 583 | c122 | 6
1 | 9 | b13 | 1
2 | 10 | c131 | 9

Any idea how to do that? (without trying to sort on the lookup column,
whose values can be random outside this test)

Best regards,

Philippe Lang