Tree Node — LeetCode 608 Python Solution

The problem

Classify every node of the tree and report its id with its type: Root when it has no parent, Leaf when it has a parent but no children, and Inner when it has both. The Tree table has one row per node: id (int, the column with unique values) and p_id (int, the id of the parent node, null for the root). The rows always describe a valid tree.

Example

Tree table:

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

Result:

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

Node 1 has no parent so it is the root, node 2 has both a parent and children so it is inner, and nodes 3, 4 and 5 never appear as a parent so they are leaves.

Python solution

import pandas as pd

def tree_node(tree: pd.DataFrame) -> pd.DataFrame:
    parents = set(tree['p_id'].dropna())
    def classify(row):
        if pd.isna(row['p_id']):
            return 'Root'
        if row['id'] not in parents:
            return 'Leaf'
        return 'Inner'
    res = tree.copy()
    res['type'] = res.apply(classify, axis=1)
    return res[['id', 'type']]

Complexity

Related problems