I'm faced with a problem.I have a ternary structured data. The relation is from child to parent, more specific a child has an parent_id. A parent shouldn't have more than 3 children. When 4th child appears it should be added to first parent's child as a child. I need a solution PostgreSQL, procedure, recursion. Any help is appreciated!
When 4th child appears it should be added to first parent's child as a child.
I suspect that new child should be added to the nearest parent's child having less than 3 childs. So the problem is reduced to the ranking of the subtree nodes along with the counting their childs.
INSERT INTO tree (id, parent_id) VALUES ( __id__ , ( WITH RECURSIVE cte AS ( SELECT 1 AS rank , t.id , ( SELECT COUNT(c.id) AS cnum FROM tree AS c WHERE c.parent_id = t.id ) AS childnum FROM tree AS t WHERE t.id = __DESIRED_PARENT_ID__ -- here is the subtree root node UNION ALL SELECT cte.rank + 1 AS rank , w.id , ( SELECT COUNT(c.id) AS cnum FROM tree AS c WHERE c.parent_id = w.id ) AS childnum FROM tree AS w JOIN cte ON w.parent_id = cte.id ) SELECT id FROM cte WHERE childnum < 3 ORDER BY rank ASC LIMIT 1 ) );
This query adds a child to the node of subtree having number of childs less than 3 and closest to the subtree root. Chosen node can be the subtree root itself if it has less than 3 childs. If more than one node of the same rank can be chosen as parent, arbitrary one is chosen. If you want to choose the node with the least number of childs you have to order that way:
ORDER BY rank ASC, childnum ASC