Tree Node

medium database sql

Problem

Tree(id, p_id). Label every node as 'Root' (p_id IS NULL), 'Leaf' (id not referenced as parent), or 'Inner'.

Inputt=[(1,null),(2,1),(3,1),(4,2),(5,2)]

Output[(1,'Root'),(2,'Inner'),(3,'Leaf'),(4,'Leaf'),(5,'Leaf')]

1 has no parent → Root; 2 has children → Inner; the rest have no children → Leaf.

rows (compact)

SELECT id,
  CASE WHEN p_id IS NULL THEN 'Root'
       WHEN id IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Inner'
       ELSE 'Leaf' END AS Type
FROM Tree;

Explanation

Each node needs one of three labels, and we can decide it from just two facts: does it have a parent, and does it have any children? A single CASE expression checks these in order.

First, if p_id IS NULL the node has no parent, so it's the Root. That check comes first because the root is special.

Otherwise, we ask whether this node's id shows up as someone else's parent: id IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL). If yes, it has children and is an Inner node; if no, it's a Leaf.

Example: node 1 has p_id = NULL → Root. Node 2 has a parent and is listed as the parent of 4 and 5 → Inner. Node 3 has a parent but parents nobody → Leaf.

Time: O(n) Space: O(n)