CODEWITHSUNDEEP
oracle-databaseplsqloracle-sqldeveloperoracle19c
yyy62103
yyy62103

Reputation: 81

need to find leaf , inner and root node

I am trying to solve this question which is on hacker rank

I got the desired output but not accepted by hacker rank

Input :

Input

Output :

Output

My trial 1 :

with tb1 as
(
   select N,P from binary_tree
), tb2 as 
(
   select N,P from binary_tree
)
select t2.N as t2_N,
case 
     when t2.P is null and t1.P is null  and t1.N is null then 'root'
     when t2.P is not null and t1.P is null and t1.N is not null then 'inner'
     ELSE 'leaf'
end as RESULT
from tb2 t2 LEFT JOIN tb1 t1 ON t2.P = t1.N order by t2.N;

My trial 2 :

with tb1 as
(
   select N,P from BST
), tb2 as 
(
   select P from BST
)
select distinct t.* from (select t1.N as tn,
case 
    when t1.N is not null and t2.P is not null and t1.P is null then 'root'
    when t1.N is not null and t2.P is not null and t1.P is not null then 'inner'
    when t1.N is not null and t2.P is null and t1.P is not null then 'leaf'
end as RESULT
from tb1 t1 LEFT JOIN tb2 t2 on t1.N = t2.P) t order by tn;

My above querys gives me desired output but not accepted

can some one figure it out why so ?

please explain me how to solve this kind of binary tree questions and any trick to solve it

Upvotes: 0

Views: 492

Answers (2)

yyy62103
yyy62103

Reputation: 81

Finally after lots of trial able to write perfect query

Solution 1 :

with tb1 as
(
   select N,P from BST
), tb2 as 
(
   select P from BST
)
select distinct t.* from (select t1.N as tn,
case 
    when t1.N is not null and t2.P is not null and t1.P is null then 'Root'
    when t1.N is not null and t2.P is not null and t1.P is not null then 'Inner'
    when t1.N is not null and t2.P is null and t1.P is not null then 'Leaf'
end as RESULT
from tb1 t1 LEFT JOIN tb2 t2 on t1.N = t2.P) t order by tn;

Solution 2 :

select 
N,
case 
     when P is null then 'root'
     when P is not null and N in ( select distinct P from BINARY_TREE ) then 'Inner'
     else 'Leaf' end as Result 
from BINARY_TREE order by N;

Solution 3 : Debugged the code of Author @mathguy who as solved using connect by

Step 1 : Getting the leaf status

SELECT
    n,
    CONNECT_BY_ISLEAF AS leaf
FROM
    binary_tree
START WITH
    p IS NULL
CONNECT BY
    p = PRIOR n
ORDER BY
    leaf;

Step 1

Step 2 : Depending upon the leaf status , defining the case statement

IF P is null -> Root 
else if `1`  -> Leaf
else 'Inner'   


SELECT
    N,
    case 
    when P is null then 'Root'
    when CONNECT_BY_ISLEAF = 1 then 'Leaf'
    else 'Inner' end as Result 
FROM
    binary_tree
START WITH
    p IS NULL
CONNECT BY
    P = PRIOR N
ORDER BY
    N;

Output :

Step 2

Upvotes: 0

user5683823
user5683823

Reputation:

I assume this is meant to test your understanding of Oracle "connect by" queries, rather than standard joins. Roots can be identified by null parent, leafs are detected by the connect_by_isleaf pseudocolumn, and all other nodes are "inner". So, the query can be written like this:

select  n,
        case when p is null             then 'Root'
             when connect_by_isleaf = 1 then 'Leaf'
             else                            'Inner' end as result
from    binary_tree
start   with p is null
connect by p = prior n
order   by n  --  if needed
;

Upvotes: 1

Related Questions