Home > Net >  Find Tree Node in SQL
Find Tree Node in SQL

Time:04-19

Hi there recently one sql question were asked in Uber which was really interesting and little bit hard as well.

The question is as below

Table: Tree

 ------------- ------ 
| Column Name | Type |
 ------------- ------ 
| id          | int  |
| p_id        | int  |
 ------------- ------ 
id is the primary key column 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 an SQL query to report the type of each node in the tree.

Return the result table ordered by id in ascending order.

The query result format is in the following example.][1]][1]

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.

Now I have already given an answer but I want to get same result with some other approaches if there is any please help me with some other approaches in this kind of questions

CodePudding user response:

select id, 
case 
    when p_id is null then "Root"
    when p_id is not null and id in (select p_id from tree) then "Inner" 
    else "Leaf"
    end as "type"

from tree

This is the solution which I have but I’m finding some another approaches please help me with this, Thanks in advance

CodePudding user response:

You can use a join as well

select distinct a.id,
   case when a.p_id is null then 'root'
        when b.id is null then 'leaf'
        else 'inner' end node_type
from tree a
left join tree b on a.id = b.p_id
order by a.id
  • Related