✏️ Explanatory Question
Level: Coding Round — A LeetCode problem; tests CASE logic combined with a subquery to detect whether a node has children.
The Puzzle: A tree table has id and p_id (parent id). Classify each node as: Root (no parent), Leaf (has a parent but no children), or Inner (has both a parent and at least one child).
tree| id | p_id |
|---|---|
| 1 | NULL |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| id | type |
|---|---|
| 1 | Root |
| 2 | Inner |
| 3 | Leaf |
| 4 | Leaf |
| 5 | Leaf |
Node 1 has no parent = Root. Node 2 has parent 1 AND children (4,5) = Inner. Node 3 has a parent but no children = Leaf.
The classification logic: Two questions decide each node's type — "Does it have a parent?" (p_id IS NULL or not) and "Does it have children?" (does any other row point to it as their parent?). A CASE combines these two checks into the three categories.
| Has parent? | Has children? | Type |
|---|---|---|
| No (p_id IS NULL) | — | Root |
| Yes | Yes | Inner |
| Yes | No | Leaf |
SELECT
id,
CASE
WHEN p_id IS NULL THEN 'Root' -- no parent
WHEN id IN (SELECT DISTINCT p_id FROM tree
WHERE p_id IS NOT NULL) THEN 'Inner' -- appears as a parent
ELSE 'Leaf' -- has parent, no children
END AS type
FROM tree
ORDER BY id; The core check — "is this id a parent?": A node has children if its id appears in the set of all p_id values. So id IN (SELECT p_id FROM tree) tests "does anyone call me their parent?" Combined with the parent check, it distinguishes Inner from Leaf. Order the CASE so Root is checked first.
SELECT
t.id,
CASE
WHEN t.p_id IS NULL THEN 'Root'
WHEN COUNT(c.id) > 0 THEN 'Inner' -- has at least one child
ELSE 'Leaf'
END AS type
FROM tree t
LEFT JOIN tree c ON c.p_id = t.id -- c = potential children of t
GROUP BY t.id, t.p_id
ORDER BY t.id; Edge case — a single-node tree: If the tree has only one row (id 1, p_id NULL), it is a Root, not a Leaf, even though it has no children. Because the WHEN p_id IS NULL THEN 'Root' branch is checked first, this is handled correctly. Ordering the CASE branches matters — always test Root before the children check.
Interviewer follow-up: "Also report each node's depth/level in the tree." → That requires walking from each node up to the root, which is a recursive CTE (Q135). Start at the roots with level 1, then recursively join children incrementing the level. The Root/Inner/Leaf classification is a single-level check; depth is a multi-level traversal — a natural bridge to recursive queries.