Classify Tree Nodes in SQL

Write a PostgreSQL query that classifies every node in a tree as Root, Inner, or Leaf.

Table

Tree contains one row per node:

Column	Type	Meaning
id	integer	Unique, non-null node identifier
pid	integer, nullable	Parent node identifier, or NULL when the node has no parent

The input represents a nonempty tree. Each non-null pid refers to the id of its parent node.

Classification rules

• Root: the node has no parent, so its pid is NULL.
• Inner: the node has a parent and at least one child. A child is a row whose pid equals this node's id.
• Leaf: the node has a parent and no children.

A root is classified as Root regardless of whether it has children, including when it is the tree's only node.

Required output

Return exactly one row per input node, with columns id and type. The type value must be exactly Root, Inner, or Leaf according to the rules above. Result rows may appear in any order.

Example

Input Tree:

id	pid
1	NULL
2	1
3	1
4	2

Expected result, shown in identifier order only for readability:

id	type
1	Root
2	Inner
3	Leaf
4	Leaf

Classify Tree Nodes in SQL

Table tree

column	type	constraints
id	INTEGER	PRIMARY KEY
pid	INTEGER

Sample data:

id	pid
3	7
42	NULL
11	0
16	90
-12	42
99	16
7	42
75	22
-8	0
90	7
0	42
5	16
4	22
61	7
22	-12
-3	90

Expected output

id	type
-12	Inner
-8	Leaf
-3	Leaf
0	Inner
3	Leaf
4	Leaf
5	Leaf
7	Inner
11	Leaf
16	Inner
22	Inner
42	Root
61	Leaf
75	Leaf
90	Inner
99	Leaf

Hints

1. Return one classification row for every input node.
2. A root remains Root whether or not it has children.