LeetCode 608: Tree Node

Problem Restatement

We are given a table called Tree.

Each row represents one node in a binary tree.

We need to classify every node into one of three types:

The result should contain:

The official problem asks to classify each node in the binary tree into these categories based on parent-child relationships. (leetcode.com)

Input and Output

Input table:

Tree

Output columns:

id, type

Example

Input:

Tree structure:

        1
       / \
      2   3
     / \
    4   5

Node classification:

Output:

First Thought: Use Parent Information

The easiest category is the root.

A node is the root when:

p_id IS NULL

because it has no parent.

The remaining nodes either:

So the key remaining question is:

“Does another row use this node as its parent?”

Key Insight

A node is an inner node if its id appears somewhere in the p_id column.

Example:

Node 2 appears in p_id, so node 2 has children.

Therefore:

This maps directly to a SQL CASE expression.

Algorithm

For each row in Tree:

1. If p_id IS NULL, classify as Root.
2. Else if the node id appears in the p_id column, classify as Inner.
3. Otherwise, classify as Leaf.

Return the result ordered by id.

SQL Solution

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

Code Explanation

The query scans every node:

FROM Tree

Then the CASE expression determines the node type.

Root Nodes

WHEN p_id IS NULL THEN 'Root'

A root node has no parent.

Inner Nodes

WHEN id IN (
    SELECT p_id
    FROM Tree
    WHERE p_id IS NOT NULL
)
THEN 'Inner'

The subquery collects all parent ids.

If a node’s id appears in this set, then some other node references it as a parent. Therefore, it has at least one child.

Leaf Nodes

ELSE 'Leaf'

If a node is not the root and does not appear as a parent, then it has no children.

So it must be a leaf.

Correctness

The query classifies each node into exactly one category.

If p_id IS NULL, the node has no parent, so it is the unique root definition.

Otherwise, if the node id appears in the p_id column, then at least one node has it as a parent. Therefore, it has at least one child and is an inner node.

Otherwise, the node has a parent but no children. Therefore, it is a leaf node.

Every node satisfies exactly one of these conditions, so the classification is complete and correct.

Complexity

Let n be the number of rows in Tree.

With an index on id and p_id, databases can optimize the membership checks efficiently.

Alternative: Left Join

We can also classify nodes by joining each node to its children.

SELECT
    t1.id,
    CASE
        WHEN t1.p_id IS NULL THEN 'Root'
        WHEN t2.id IS NOT NULL THEN 'Inner'
        ELSE 'Leaf'
    END AS type
FROM Tree AS t1
LEFT JOIN Tree AS t2
    ON t1.id = t2.p_id
GROUP BY t1.id, t1.p_id
ORDER BY t1.id;

The join:

t1.id = t2.p_id

matches a node with its children.

If a match exists, the node has children and becomes an inner node.

Testing

Sample data:

CREATE TABLE Tree (
    id INT,
    p_id INT
);

INSERT INTO Tree (id, p_id) VALUES
    (1, NULL),
    (2, 1),
    (3, 1),
    (4, 2),
    (5, 2);

Expected output:

Additional case:

TRUNCATE TABLE Tree;

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

Expected output:

Single-node trees still classify correctly because the node has no parent.