Skip to main content
Talentd

Binary Tree Nodes - Solution & Explanation

MediumPremiumFree on FleetCodeDatabase4 min readAsked at: Google
Practice this problem

Problem Statement

Table: Tree

+-------------+------+ 
| Column Name | Type | 
+-------------+------+ 
| N           | int  | 
| P           | int  |
+-------------+------+
N is the column of unique values for this table.
Each row includes N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

Write a solution to find the node type of the Binary Tree. Output one of the following for each node:

  • Root: if the node is the root node.
  • Leaf: if the node is the leaf node.
  • Inner: if the node is neither root nor leaf node.

Return the result table ordered by node value in ascending order.

The result format is in the following example.

 

Example 1:

Input: 
Tree table:
+---+------+
| N | P    | 
+---+------+
| 1 | 2    |
| 3 | 2    | 
| 6 | 8    | 
| 9 | 8    | 
| 2 | 5    | 
| 8 | 5    | 
| 5 | null | 
+---+------+
Output: 
+---+-------+
| N | Type  | 
+---+-------+
| 1 | Leaf  | 
| 2 | Inner |
| 3 | Leaf  |
| 5 | Root  |
| 6 | Leaf  |
| 8 | Inner |
| 9 | Leaf  |    
+---+-------+
Explanation: 
- Node 5 is the root node since it has no parent node.
- Nodes 1, 3, 6, and 9 are leaf nodes because they don't have any child nodes.
- Nodes 2, and 8 are inner nodes as they serve as parents to some of the nodes in the structure.

 

Note: This question is the same as 608: Tree Node.

Approach Overview

Problem Overview: Given a table representing a tree, each row stores a node and its parent. Your task is to classify every node as Root, Inner, or Leaf. A node is Root if it has no parent, Inner if it has at least one child, and Leaf if it has no children.

Approach 1: Self Left Join (O(n) time, O(1) extra space)

This problem is naturally solved with a self join. Treat the table as two logical copies: one representing the current node and the other representing potential child nodes. Perform a LEFT JOIN where the parent node's id matches the child's parent_id. If a row from the second table exists, the node has at least one child.

Use a CASE expression to classify nodes. If parent_id IS NULL, the node is the Root. If the join finds a matching child row, the node is an Inner node. Otherwise, it has no children and must be a Leaf. Because joins may produce duplicate rows for nodes with multiple children, apply GROUP BY on the node id to keep one result per node.

This approach works because a self join allows you to check parent-child relationships directly within the same table. The database scans the table once and resolves relationships through the join, resulting in roughly O(n) time depending on indexing. Extra memory usage is constant since classification happens during query execution.

SQL tree problems often rely on the same idea: compare rows within the same table using joins. Understanding SQL joins, especially self joins, is essential when working with hierarchical data stored in relational database tables.

Recommended for interviews: The self LEFT JOIN approach is the expected solution. It demonstrates that you understand hierarchical relationships in relational tables and know how to detect child rows using joins. Simpler conditional checks identify the root node, while the join determines whether the node is inner or leaf.

Solution

If a node's parent is null, then it is a root node; if a node is not the parent of any node, then it is a leaf node; otherwise, it is an internal node.

Therefore, we use left join to join the Tree table twice, with the join condition being t1.N = t2.P. If t1.P is null, then t1.N is a root node; if t2.P is null, then t1.N is a leaf node; otherwise, t1.N is an internal node.

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Left JoinO(n)O(1)Best general solution for identifying parent-child relationships directly in SQL
Self Join + AggregationO(n)O(1)Useful when counting children explicitly or when duplicates from joins must be aggregated

Video Solution

Leetcode MEDIUM 3054 - Binary Tree Nodes CASE WHEN DSA SQL - Explained by Everyday Data Science • Everyday Data Science • 500 views views

Frequently Asked Questions

Is Binary Tree Nodes easy or hard?
Binary Tree Nodes is generally considered Medium because it requires recognizing a self join pattern in SQL. Once you understand how to detect child rows with a LEFT JOIN, the classification logic becomes straightforward.
Binary Tree Nodes Python/Java solution
This problem is typically solved using SQL rather than Python or Java because the data already exists in a database table. The core logic relies on a self LEFT JOIN and CASE expression to classify nodes directly within the query.
How to solve Binary Tree Nodes in O(n)?
Use a self LEFT JOIN between the tree table and itself on id = parent_id. This reveals whether a node has child rows. Combine that with a CASE expression: parent_id IS NULL means Root, a matched child row means Inner, otherwise Leaf. The database processes rows in a single join pass, giving about O(n) complexity.
What is the best approach for Binary Tree Nodes?
The best approach uses a SQL self LEFT JOIN. Join the table with itself where a node's id matches another row's parent_id to detect children. Then use a CASE statement to label nodes as Root (no parent), Inner (has children), or Leaf (no children). This runs in roughly O(n) time depending on indexing.
Is Binary Tree Nodes asked at Google/Amazon/Meta?
SQL hierarchy and tree classification problems appear in database-focused interviews at companies like Amazon and Meta. Variations of this problem test understanding of self joins, CASE expressions, and relational modeling of hierarchical data.
What data structure is used in Binary Tree Nodes?
The logical structure is a tree, but it is stored in a relational database table using parent-child references. Each row stores a node id and a parent_id. SQL joins are then used to reconstruct relationships between nodes.
What is the time complexity of Binary Tree Nodes?
The typical SQL solution using a self LEFT JOIN runs in O(n) time for n rows in the tree table. The database scans rows and resolves the join to identify child relationships. Space complexity is O(1) extra since the classification happens within the query.

Ready to solve this problem?

Practice Binary Tree Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary