1def classify_nodes(nodes):
2    child_count = dict()
3    types = dict()
4
5    for node in nodes:
6        id, p_id = node
7        if p_id != None:
8            child_count[p_id] = child_count.get(p_id, 0) + 1
9        types[id] = "Leaf"
10
11    for node in nodes:
12        id, p_id = node
13        if p_id is None:
14            types[id] = "Root"
15        elif id in child_count:
16            types[id] = "Inner"
17
18    for id in types:
19        print(id, types[id])
20
21nodes = [(1, None), (2, 1), (3, 1), (4, 2), (5, 2)]
22classify_nodes(nodes)

using System.Collections.Generic;

public class Node {
    public int Id, PId;
    public Node(int id, int pId) { Id = id; PId = pId; }
}

public class TreeNode {
    public static void ClassifyNodes(List<Node> nodes) {
        var isChild = new HashSet<int>();

        foreach (var node in nodes) {
            if (node.PId != -1) isChild.Add(node.PId);
        }

        foreach (var node in nodes) {
            if (node.PId == -1) {
                Console.WriteLine(node.Id + " Root");
            } else if (isChild.Contains(node.Id)) {
                Console.WriteLine(node.Id + " Inner");
            } else {
                Console.WriteLine(node.Id + " Leaf");
            }
        }
    }

    public static void Main() {
        List<Node> nodes = new List<Node> {
            new Node(1, -1), new Node(2, 1), new Node(3, 1), new Node(4, 2), new Node(5, 2)
        };
        ClassifyNodes(nodes);
    }
}