0

I have a table with two columns: child and parent. This table represents a tree kind structure having multiple trees. Given any child, i need to find its root. In other words, I need to get the parent of that child, and then the parent of the parent and so on until it reaches the root of that child.

child    parent
1        2
2        3
9        10
3        4
4        5
5        255

Here, we have two trees. One starts from 255(root) and ends at 1(leaf). 255 -> 5 -> 4 -> 3 -> 2 -> 1. And the second one starts at 10 and ends at 9. For ex: if 3 is given then it needs to find the root which on this case would be 255. I am really new to the SQL world. My idea would be to recursively traverse the parent column for the child until if there is no entry in the child column for some parent on the way and return that parent. Is there a way to do that in SQL, especially in postgres.?

SpaceyBot
  • 482
  • 1
  • 4
  • 20
  • 1
    Unrelated, but: using a "magic number" like 255 to indicate the absence of a parent is a bad idea. You should be storing NULL instead –  May 03 '19 at 08:04

1 Answers1

1

For such cases, you can use recursive queries. The only problem is that recursive queries are not very efficient in Postgres, so you can use this approach for small volumes of data only. Heres sample:

create table tree (id integer, parent integer);
insert into tree values(1, null);
insert into tree values(2, 1);
insert into tree values(3, 1);
insert into tree values(4, 3);
insert into tree values(5, 2);

insert into tree values(10, null);
insert into tree values(20, 10);
insert into tree values(30, 10);
insert into tree values(40, 30);
insert into tree values(50, 20);

with recursive parentsearch as (
 select id, parent as parent_id from tree where id = :leaf_id
 union
 select t.id, t.parent as parent_id from tree t join parentsearch ps on t.id=ps.parent_id
)
select * from parentsearch where parent_id is null;
Vicctor
  • 803
  • 6
  • 13
  • Thanks a lot. Just OOC, if the child_id is not given, then how would you find out all the tree combination (root-leaf) ? – SpaceyBot May 03 '19 at 09:26
  • First, you need to consider that's it's easy to find roots (as they have a parent which is never used as child_id [or id in my sample]) For simplicity I will consider it's always null. So then you have just to traverse all possible paths in the tree starting from every known root. In PG you can keep the traversed paths in the array type. Then you have to filter results, and find only those which ends with the last leaf in the tree - just check if given child_id is never used as a parent. So finally you will end up with something like in this fiddle: http://sqlfiddle.com/#!17/69fe39/24 – Vicctor May 03 '19 at 13:09