# LeetCode 608: Tree Node

## Problem Restatement

We are given a table called `Tree`.

Each row represents one node in a binary tree.

| Column | Type | Meaning |
|---|---|---|
| `id` | int | Node id |
| `p_id` | int | Parent node id |

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

| Type | Meaning |
|---|---|
| `Root` | The node has no parent |
| `Leaf` | The node has no children |
| `Inner` | The node has both a parent and at least one child |

The result should contain:

| Column | Meaning |
|---|---|
| `id` | Node id |
| `type` | Root, Leaf, or Inner |

The official problem asks to classify each node in the binary tree into these categories based on parent-child relationships. ([leetcode.com](https://leetcode.com/problems/tree-node/?utm_source=chatgpt.com))

## Input and Output

Input table:

```sql
Tree
```

Output columns:

```sql
id, type
```

## Example

Input:

| id | p_id |
|---:|---:|
| 1 | null |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |

Tree structure:

```text
        1
       / \
      2   3
     / \
    4   5
```

Node classification:

| Node | Reason | Type |
|---:|---|---|
| 1 | No parent | Root |
| 2 | Has parent and children | Inner |
| 3 | Has parent but no children | Leaf |
| 4 | Has parent but no children | Leaf |
| 5 | Has parent but no children | Leaf |

Output:

| id | type |
|---:|---|
| 1 | Root |
| 2 | Inner |
| 3 | Leaf |
| 4 | Leaf |
| 5 | Leaf |

## First Thought: Use Parent Information

The easiest category is the root.

A node is the root when:

```sql
p_id IS NULL
```

because it has no parent.

The remaining nodes either:

| Possibility | Meaning |
|---|---|
| Have children | Inner |
| Have no children | Leaf |

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:

| id | p_id |
|---:|---:|
| 2 | 1 |
| 4 | 2 |
| 5 | 2 |

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

Therefore:

| Condition | Type |
|---|---|
| `p_id IS NULL` | Root |
| `id IN (SELECT p_id ...)` | Inner |
| Otherwise | Leaf |

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

```sql
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:

```sql
FROM Tree
```

Then the `CASE` expression determines the node type.

### Root Nodes

```sql
WHEN p_id IS NULL THEN 'Root'
```

A root node has no parent.

### Inner Nodes

```sql
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

```sql
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`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` worst case | The `IN` subquery may be checked for many rows |
| Space | `O(n)` | The subquery result may store parent ids |

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.

```sql
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:

```sql
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:

```sql
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:

| id | type |
|---:|---|
| 1 | Root |
| 2 | Inner |
| 3 | Leaf |
| 4 | Leaf |
| 5 | Leaf |

Additional case:

```sql
TRUNCATE TABLE Tree;

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

Expected output:

| id | type |
|---:|---|
| 10 | Root |

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