Table: Tree
+-------------+------+ | Column Name | Type | +-------------+------+ | id | int | | p_id | int | +-------------+------+ id is the column with unique values for this table. Each row of this table contains information about the id of a node and the id of its parent node in a tree. The given structure is always a valid tree.
Each node in the tree can be one of three types:
Write a solution to report the type of each node in the tree.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Tree table: +----+------+ | id | p_id | +----+------+ | 1 | null | | 2 | 1 | | 3 | 1 | | 4 | 2 | | 5 | 2 | +----+------+ Output: +----+-------+ | id | type | +----+-------+ | 1 | Root | | 2 | Inner | | 3 | Leaf | | 4 | Leaf | | 5 | Leaf | +----+-------+ Explanation: Node 1 is the root node because its parent node is null and it has child nodes 2 and 3. Node 2 is an inner node because it has parent node 1 and child node 4 and 5. Nodes 3, 4, and 5 are leaf nodes because they have parent nodes and they do not have child nodes.
Example 2:
Input: Tree table: +----+------+ | id | p_id | +----+------+ | 1 | null | +----+------+ Output: +----+-------+ | id | type | +----+-------+ | 1 | Root | +----+-------+ Explanation: If there is only one node on the tree, you only need to output its root attributes.
Note: This question is the same as 3054: Binary Tree Nodes.
The idea is to identify the type of each node by examining the parent-child relationship. Specifically, to identify:
Steps:
The C solution defines a Node structure to store the id and p_id information. It uses an additional array to count the children of each node. By examining the relationship between p_id and id, we can easily determine the type of each node. Lastly, we set the type as 'Leaf', 'Inner', or 'Root' in the output list of ResultNode structures.
C++
Java
Python
C#
JavaScript
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.
This approach centers around identifying nodes type by tracking parent relationships directly:
Steps:
For C, the solution distinguishes between node types by utilizing a boolean-like array, where 'isChild' flags determine if a node is referenced as a parent elsewhere. This inventive use of children status quickly streamlines the decision of the node type, printing results accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n)
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Approach 1: Using Child Count | Time Complexity: O(n), where n is the number of nodes, as we traverse through the list of nodes usually once or twice. |
| Approach 2: Using Parent Lookup | Time Complexity: O(n) |
Balanced Binary Tree - Leetcode 110 - Python • NeetCode • 306,385 views views
Watch 9 more video solutions →Practice Tree Node with our built-in code editor and test cases.
Practice on FleetCode