Tree Node - Solution & Explanation
Problem Statement
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:
- "Leaf": if the node is a leaf node.
- "Root": if the node is the root of the tree.
- "Inner": If the node is neither a leaf node nor a root node.
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.
Approach Overview
Problem Overview: You are given a table Tree(id, p_id) representing a tree structure. Each row is a node, and p_id points to its parent. The task is to classify every node as Root, Inner, or Leaf depending on whether it has a parent and whether it has children.
Approach 1: Using Child Count (O(n) time, O(1) extra space)
This approach determines the node type by checking how many children each node has. Perform a self-reference lookup where a node’s id appears as another row’s p_id. If p_id IS NULL, the node is the Root. If the node appears in the child list (meaning at least one row has p_id = id), it is an Inner node. Otherwise, it is a Leaf. SQL typically uses GROUP BY or LEFT JOIN with a child count to detect this. With proper indexing on id and p_id, the database scans the table once and performs efficient lookups, giving roughly O(n) time complexity and constant auxiliary space since the work happens inside the query engine. This approach is clear and scales well for larger datasets.
Approach 2: Using Parent Lookup (O(n) time, O(1) extra space)
Instead of counting children, this method directly checks membership relationships. First identify the root using p_id IS NULL. For the remaining rows, determine if a node is referenced as a parent anywhere in the table. If a node’s id appears in the set of p_id values, it must have at least one child, making it an Inner node. If it does not appear in that set, it is a Leaf. This is usually implemented with IN, NOT IN, or EXISTS subqueries. The database engine internally builds a lookup structure for the parent IDs, so the classification can still be resolved in about O(n) time. The query is concise and easy to reason about when working with relational hierarchies.
Problems like this frequently appear in database interview rounds because they test how well you understand hierarchical data in relational tables. You are essentially deriving structural information from a flat table using SQL operations such as filtering, membership checks, and self-references. Knowledge of SQL joins and subqueries is essential, especially when modeling parent-child relationships similar to self joins.
Recommended for interviews: The child-count or self-join approach is typically preferred because it clearly shows how you derive children from the table structure. The parent lookup version is slightly shorter and perfectly valid, but interviewers often expect you to reason explicitly about parent-child relationships using joins or grouped counts.
Approach 1: Approach 1: Using Child Count
The idea is to identify the type of each node by examining the parent-child relationship. Specifically, to identify:
- The root node, which does not have a parent.
- Inner nodes, which have children.
- Leaf nodes, which do not have any children.
Steps:
- Traverse the tree table to build a map where each id points to its type.
- Use a helper data structure to count the number of children for each node.
- Scan the table again to finalize node types based on the count data.
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.
Complexity
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.
Approach 2: Approach 2: Using Parent Lookup
This approach centers around identifying nodes type by tracking parent relationships directly:
- Root nodes are explicitly those which have no parents.
- Inner nodes have a parent (non-null p_id) and also have children, usually derived by inversion of role (found as a parent somewhere).
- Leaf nodes aren't found as a parent in any other nodes.
Steps:
- Construct a parent dictionary to easily distinguish inner from leaf nodes.
- Assign initial types by checking the node's p_id and presence in the parent dictionary.
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.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Conditional Statements + Subquery
We can use the CASE WHEN conditional statement to determine the type of each node as follows:
- If a node's
p_idisNULL, then it is a root node. - Otherwise, if a node is the parent node of another node (we use a subquery to determine this), then it is an internal node.
- Otherwise, it is a leaf node.
Code
MySQL
Complexity Comparison
| 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) |
| Conditional Statements + Subquery | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Child Count via Self Join / Group By | O(n) | O(1) | Best for clearly identifying nodes with children using joins or grouped counts |
| Parent Lookup with IN / EXISTS | O(n) | O(1) | Shorter SQL when simply checking if a node appears as a parent |
Video Solution
Solving SQL Interview Query | Find Tree Node type using SQL • techTFQ • 32,735 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Tree Node easy or hard?
Tree Node Python/Java solution
How to solve Tree Node in O(n)?
What is the best approach for Tree Node?
Is Tree Node asked at Google/Amazon/Meta?
What data structure is used in Tree Node?
What is the time complexity of Tree Node?
Ready to solve this problem?
Practice Tree Node with our built-in code editor and test cases.
Practice on FleetCode