Katkat
Back

Classify Tree Nodes in SQL

OracleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenData Manipulation (SQL/Python)

Last updated

Tests the ability to write conditional logic and subqueries/joins in SQL to classify hierarchical tree nodes into 'Root', 'Inner', or 'Leaf'.

Problem Statement

You are given a table named tree representing a binary tree or general tree structure where each row contains a node's ID and its parent's ID.

Write an SQL query (PostgreSQL syntax) to classify each node into one of three categories:

  • Root: The node has no parent (p_id IS NULL).
  • Inner: The node has a parent and has at least one child node.
  • Leaf: The node has a parent but has no children.

Return the result table ordered by id in ascending order.

Schema Definition

CREATE TABLE tree (
    id INT PRIMARY KEY,
    p_id INT
);
  • id: The unique identifier of the node.
  • p_id: The identifier of the parent node. If p_id IS NULL, this node is the root.

Example 1

Input:

+----+------+
| 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 has no parent (p_id IS NULL), so it is a Root.
  • Node 2 has parent 1 and children 4 and 5, so it is an Inner node.
  • Nodes 3, 4, and 5 have parents but no children, so they are Leaf nodes.

Example 2 (Single Node)

Input:

+----+------+
| id | p_id |
+----+------+
| 1  | null |
+----+------+

Output:

+----+------+
| id | type |
+----+------+
| 1  | Root |
+----+------+

Constraints

  • The tree contains between 1 and 100,000 nodes.
  • Each node has at most one parent.
  • The input graph is guaranteed to be a valid tree with exactly one root.

Edge Cases

  • A single-node tree should classify that node as Root, not Leaf.
  • Large tables where IN (SELECT p_id FROM tree) might evaluate slowly if NULL handling or indexing isn't considered.

Hints

Hint 1

A CASE statement is ideal for evaluating the three mutually exclusive conditions in order.

Hint 2

Be careful when using `NOT IN (SELECT p_id FROM tree)` because if the subquery returns any `NULL` value, `NOT IN` will evaluate to `UNKNOWN` for all rows.

Hint 3

Instead of `NOT IN`, consider using `EXISTS`, a `LEFT JOIN`, or filtering out `NULL`s in the subquery.

Follow-up questions

  • How does PostgreSQL handle `NULL` values inside an `IN` vs. `EXISTS` subquery, and what are the performance implications for large datasets?
  • How would you modify the query to return the depth (distance from root) for each node using a recursive Common Table Expression (CTE)?
  • If the table contains millions of rows, what index or indexes would you create to optimize this query?