Node Classification

The shown NOT IN approach must exclude NULL parent IDs. A correlated NOT EXISTS solution is often easier to reason about and is portable.

Problem Statement

Many real systems are organized as trees, file folders, company org charts, comment threads on a forum, and so on. For these systems to be rendered or processed correctly, software often needs to know what kind of node it’s looking at: is it the very top of the tree, a node buried somewhere in the middle, or an end point with nothing underneath it?

Business context Think of a file explorer. Folders that contain other folders need a different icon or behavior (expandable) than files that contain nothing (not expandable). The same idea applies to org charts, where a CEO node behaves differently from a manager node, which behaves differently from an individual contributor with no direct reports.

Goal For every node in a tree, label it as one of three types: Root, Leaf, or Inner.

Input A table representing parent-child relationships between nodes.

Output Every node’s ID along with its classified type.

Table Structure

Table: Tree

Column Meaning

• id — the unique ID of a node, and the primary key of this table
• p_id — the ID of this node’s parent. If p_id is NULL, the node has no parent at all, meaning it sits at the very top of the tree

Important Notes

• The table is guaranteed to form a valid tree: it’s connected (every node can be traced back to the root) and acyclic (no loops), with exactly one root.
• A node is classified using three simple rules:
  • Root → p_id IS NULL (no parent)
  • Leaf → the node never shows up as someone else’s parent (no children)
  • Inner → the node has a parent AND also has at least one child of its own
• These three categories cover every possible node. A node cannot be two things at once, since having no parent (Root) automatically rules out needing to check for children, and once you know a node has a parent, checking for children is what separates Leaf from Inner.
• The output order does not matter, so there’s no need for an ORDER BY here, unlike Problem 3.

Example

Example 1 — Input

Expected Output

CREATE TABLE Tree (id INTEGER, p_id INTEGER);
INSERT INTO Tree VALUES
  (10, NULL);

Explanation: Node 10 has no parent, so it is immediately classified as Root. With only one row, there’s nothing else to compare it against.

Example 2 — Input

Expected Output

Explanation

• Node 1: p_id is NULL → Root
• Node 2: has a parent (node 1) and also has children (nodes 4 and 5 both list node 2 as their parent) → Inner
• Node 3: has a parent (node 1), but no other row lists node 3 as a parent → Leaf
• Node 4 and Node 5: both have a parent (node 2), but neither appears as a parent anywhere → Leaf

Intuition

Picture a family tree drawn on paper. At the very top sits one person with no parents shown above them, that’s your Root.

At the very bottom, you have people with no children drawn below them, those are your Leaves.

Everyone else, sitting somewhere in the middle, has both a parent above them and at least one child below them, those are your Inner nodes.

The tricky part of this problem isn’t understanding the three categories, it’s realizing that checking “does this node have children” requires looking at the entire table, not just the current row. A single row only tells you about a node’s own parent (via p_id), it never directly tells you if that node is somebody else’s parent. To know that, you have to search the whole table for any row where this node’s ID shows up in the p_id column.

Mental Model

Imagine every row in the table as an index card with two things written on it: “my ID” and “my parent’s ID.”

To figure out if a person is a Root, you only need to glance at their own card, if the parent field is blank, done, they’re Root.

But to figure out if someone is a Leaf or Inner, you can’t just look at their own card. You need to spread out every single card on the table and ask: “does anyone else’s card mention my ID as their parent?” If nobody’s card mentions you, you’re a Leaf, nobody depends on you. If at least one card does mention you, and your own card also has a parent listed, you’re Inner, you sit somewhere in the middle of the chain.

This is exactly why this problem needs a subquery, one part of the check needs information gathered from across the whole table, not just the current row being evaluated.

Thought Process

Before writing SQL, work through the logic in plain language first.

1. What’s the simplest check? Root. You only need to look at one column on one row: is p_id NULL?
2. What’s the next check, if it’s not Root? Now you know the node has a parent. The remaining question is whether it also has children.
3. How do you check for children? You need to know: does this node’s id ever appear anywhere in the p_id column of the table? If yes, it has at least one child.
4. If it doesn’t have children, what does that make it? Leaf, since it already has a parent (it’s not Root), and nothing depends on it (no children).
5. If it does have children, what does that make it? Inner, since it has both a parent and children.
6. Does the order of these checks matter? Yes. Root should be checked first, since a node with no parent can only be Root, it doesn’t even make sense to ask about its children status separately, that scenario is already fully covered by the Root category.

Once you see it this way, the whole thing becomes a three-branch CASE, where the Leaf check needs a small subquery to look across the whole table.

Approach

Step 1: Identify the Root node Directly check p_id IS NULL. This needs no subquery, since it only depends on the current row’s own value.

Step 2: Identify Leaf nodes A node is a Leaf if its id never shows up in the p_id column of any row in the table. This requires checking the current node’s ID against a list of every parent ID that exists anywhere in the table, which means using a subquery.

Step 3: Identify Inner nodes If a node is not Root (it has a parent) and is not a Leaf (it does have children), then by process of elimination, it must be Inner. This means Inner doesn’t need its own explicit check, it can simply be the ELSE branch.

Step 4: Combine all three into a single CASE Check Root first, then Leaf, and let Inner fall through as ELSE, since every node that reaches that point must have both a parent and children.

SQL Query

SELECT
    t.id,
    CASE
        -- A node with no parent is the Root of the tree
        WHEN t.p_id IS NULL THEN 'Root'
        -- A node is a Leaf if its id never appears as someone else's p_id
        WHEN t.id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'
        -- Anything left over has both a parent and children, so it's Inner
        ELSE 'Inner'
    END AS type
FROM
    Tree t;

Query Explanation

• t.p_id IS NULL — the very first check. If true, the node has no parent, so it must be the Root. This is checked before anything else, since Root is the simplest and most exclusive category.
• SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL — this subquery collects every distinct parent ID that actually exists in the table. In other words, it builds a list of “every node that has at least one child.” The WHERE p_id IS NOT NULL part is important, it prevents NULL from accidentally ending up in this list, which could cause unexpected behavior with NOT IN.
• t.id NOT IN (…) — checks whether the current node’s ID is missing from that list of parent IDs. If it’s missing, nobody has this node as their parent, meaning it has no children, so it’s a Leaf.
• ELSE ‘Inner’ — anything that reaches this point already failed the Root check (so it has a parent) and failed the Leaf check (so it does have children). Both conditions being true at once is exactly the definition of Inner, so no separate condition needs to be written for it.
• FROM Tree t — the alias t is used so the outer query and the subquery can both reference the Tree table clearly without confusion.

Dry Run

Original table

↓

Step 1: Build the “has children” list (the subquery)SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL scans the p_id column and collects every distinct non-NULL value:

p_id values found

1

2

This means: node 1 has at least one child, and node 2 has at least one child. Every other node does not appear in this list at all.

↓

Step 2: Evaluate each row against the CASE conditions

↓

Final output

SQL Execution Flow

Subquery runs first:
SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL
   ↓
Produces a list of every node ID that has at least one child
   ↓
FROM Tree t (outer query)
   ↓
For each row, check p_id IS NULL → Root?
   ↓
If not Root, check if t.id is missing from the "has children" list → Leaf?
   ↓
If neither Root nor Leaf → Inner (ELSE)
   ↓
SELECT t.id, type
   ↓
Return final output (order does not matter)

Logically, the subquery only needs to be conceptually evaluated once to build the list of parent IDs, though depending on the database’s query optimizer, the actual execution plan might run it differently under the hood. For understanding purposes, it’s easiest to think of the subquery as producing one static list that every row’s Leaf check then compares against.

Time Complexity

Time Complexity: O(n) for the subquery + O(n) for the outer scan, so overall roughly O(n) to O(n log n) depending on how the database implements the NOT IN check internally (some databases turn this into a hash lookup, others may use a nested loop, which could behave closer to O(n²) on very large tables without proper indexing).

Space Complexity: O(n) The subquery’s result (the list of distinct parent IDs) needs to be held somewhere in memory or temporary storage while the outer query checks every row against it.

Why: Unlike Problems 1 through 3, this query cannot make its decision using only the current row’s own values. It needs a separate pass over the table to build the list of “known parents” first, and then a second logical pass to compare every row’s ID against that list. This two-step nature is what makes this query more expensive than the earlier ones, and it’s exactly why indexing the p_id column can make a real difference on large trees.

Common Mistakes to Avoid

Mistake 1: Forgetting to exclude NULL from the subquery

Why it happens: It’s easy to write the subquery without thinking about what happens when p_id itself contains NULL values.

Wrong:

WHEN t.id NOT IN (SELECT DISTINCT p_id FROM Tree) THEN 'Leaf'

If even one row in the whole table has p_id as NULL (which the Root row always will), then NOT IN can behave unexpectedly. In standard SQL, if the list being checked against contains any NULL, NOT IN can end up returning UNKNOWN for every single row, effectively breaking the Leaf check entirely for the whole query.

Correct:

WHEN t.id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'

Always filter out NULLs before using a column inside NOT IN.

Mistake 2: Checking Leaf before Root

Why it happens: It might seem like the order of WHEN conditions doesn’t matter here, but it does.

Wrong (conceptually):

CASE
    WHEN t.id NOT IN (SELECT DISTINCT p_id FROM Tree WHERE p_id IS NOT NULL) THEN 'Leaf'
    WHEN t.p_id IS NULL THEN 'Root'
    ELSE 'Inner'
END

This can accidentally label a Root node as Leaf if that Root also happens to have no children (a tree with only one node, for example), since the Leaf check would match first and the Root check would never even get evaluated.

Correct: Always check Root first, since it is the most specific and exclusive condition, then check Leaf, and let Inner be the natural fallback.

Mistake 3: Using a JOIN instead of a subquery and ending up with duplicate rows

Why it happens: Some beginners try to solve this with a LEFT JOIN between the table and itself, matching on p_id, but forget that a node with multiple children will produce multiple matching rows.

Wrong (conceptually):

SELECT t1.id, ...
FROM Tree t1
LEFT JOIN Tree t2 ON t1.id = t2.p_id

Without a GROUP BY or DISTINCT, this produces one output row per child match, so a node with two children (like node 2 in the example) would show up twice in the raw output, which does not match the expected one-row-per-node output.

Correct: Either use the NOT IN subquery approach shown in the main solution, or if using a JOIN, remember to GROUP BY the original node’s id afterward to collapse duplicate rows back into one.

Mistake 4: Assuming a node with no children is automatically the same as a Root

Why it happens: Both Root and Leaf can feel like “special” or “edge case” nodes, which can cause confusion between the two.

Why it matters: Root is about having no parent. Leaf is about having no children. These are two completely independent facts about a node, and a single node could theoretically be both if the tree only had one node total, in which case the Root check should still take priority, since a lone node with no parent is still fundamentally the Root of that tree.

Correct: Keep the two concepts mentally separate: Root looks at p_id on the current row, Leaf looks at every other row’s p_id values.

Mistake 5: Forgetting DISTINCT in the subquery

Why it happens: It doesn’t cause wrong results here since NOT IN only cares whether a value exists in the list, not how many times, but skipping DISTINCT means the database might unnecessarily process duplicate values internally.

Wrong (not incorrect, but wasteful on large trees):

SELECT p_id FROM Tree WHERE p_id IS NOT NULL

If a node has many children, its ID will appear repeatedly in the p_id column, and without DISTINCT, the subquery returns every one of those duplicates.

Correct: Use SELECT DISTINCT p_id ... to keep the list of parent IDs clean and avoid unnecessary duplication, which can help performance on very large hierarchical tables.

Further Questions

• “How would you rewrite this using a LEFT JOIN instead of a subquery with NOT IN?”
• “What would happen to this query if the table accidentally contained more than one root node?”
• “How would you count how many direct children each node has, instead of just labeling them Leaf/Inner/Root?”
• “How would you find the depth of each node in the tree, not just its type?”
• “Why can using NOT IN with a list that might contain NULL be dangerous? How would you rewrite it more safely using NOT EXISTS?”

Similar Problems

• Problems involving self-joins on hierarchical data, such as finding a node’s siblings, ancestors, or descendants
• Recursive CTEs, which extend this same tree idea to answer questions like “how many levels deep is this node” or “list every descendant of a given node”
• Problems that require subqueries specifically to check the presence or absence of a value across an entire table, not just a single row

Key SQL Concepts Learned

Pattern Recognition

When should you immediately think of this approach?

• Need to classify a row based on a fact that isn’t visible on that row alone, but depends on the rest of the table → use a subquery inside the CASE condition
• Working with a self-referencing table (a table where one column points to another row’s ID in the same table) → this is almost always a tree or hierarchy problem
• Need to check “does this ID appear anywhere else in the table” → NOT IN (subquery) or NOT EXISTS (correlated subquery), both work, but NOT EXISTS is often safer around NULLs
• A subquery will be used inside NOT IN → always filter out NULL from that subquery’s result first
• Multiple classification categories where one is simply “whatever’s left over” → let that category be the ELSE branch instead of writing an explicit condition for it