Sponsored
Sponsored
The idea is to identify the type of each node by examining the parent-child relationship. Specifically, to identify:
Steps:
Time Complexity: O(n), where n is the number of nodes, as we traverse through the list of nodes usually once or twice.
Space Complexity: O(n), used by the children count array and the result array.
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)The Python solution leverages dictionaries to count children and classify node types. By iterating over the list of nodes, it first initializes each node as a 'Leaf', then updates its status to 'Root' or 'Inner' based on its structural position in the tree.
This approach centers around identifying nodes type by tracking parent relationships directly:
Steps:
Time Complexity: O(n)
Space Complexity: O(n)
Python's implementation uses a set to distinguish between nodes that are involved as parents. This effectively allows rapid classification of node status, ensuring concise filtering of data.