1import java.util.*;
2
3class Node {
4    int id, p_id;
5    Node(int id, int p_id) { this.id = id; this.p_id = p_id; }
6}
7
8public class TreeNode {
9    public static void classifyNodes(List<Node> nodes) {
10        Map<Integer, Integer> childCount = new HashMap<>();
11        Map<Integer, String> types = new HashMap<>();
12
13        for (Node node : nodes) {
14            if (node.p_id != -1) {
15                childCount.put(node.p_id, childCount.getOrDefault(node.p_id, 0) + 1);
16            }
17            types.put(node.id, "Leaf");
18        }
19
20        for (Node node : nodes) {
21            if (node.p_id == -1) {
22                types.put(node.id, "Root");
23            } else if (childCount.getOrDefault(node.id, 0) > 0) {
24                types.put(node.id, "Inner");
25            }
26        }
27
28        for (Node node : nodes) {
29            System.out.println(node.id + " " + types.get(node.id));
30        }
31    }
32
33    public static void main(String[] args) {
34        List<Node> nodes = Arrays.asList(
35            new Node(1, -1),
36            new Node(2, 1),
37            new Node(3, 1),
38            new Node(4, 2),
39            new Node(5, 2)
40        );
41        classifyNodes(nodes);
42    }
43}

#include <vector>
#include <unordered_set>

struct Node {
    int id, p_id;
};

void classifyNodes(const std::vector<Node>& nodes) {
    std::unordered_set<int> isChild;

    for (const auto& node : nodes) {
        if (node.p_id != -1) {
            isChild.insert(node.p_id);
        }
    }

    for (const auto& node : nodes) {
        if (node.p_id == -1) {
            std::cout << node.id << " Root" << std::endl;
        } else if (isChild.count(node.id)) {
            std::cout << node.id << " Inner" << std::endl;
        } else {
            std::cout << node.id << " Leaf" << std::endl;
        }
    }
}

int main() {
    std::vector<Node> nodes = {{1, -1}, {2, 1}, {3, 1}, {4, 2}, {5, 2}};
    classifyNodes(nodes);
    return 0;
}