Can anyone please explain this solution of hacker rank Binary Tree Nodes?

Question

SELECT N, CASE WHEN P IS NULL THEN 'Root' 
WHEN(SELECT COUNT(*) FROM BST WHERE P = b.N) > 0 THEN 'Inner'
ELSE 'Leaf'
END
FROM bst b 
ORDER BY N;`

Can anyone please explain this solution of hacker rank Binary Tree Nodes? Why there are p=b.n and why it does not work when I use from bst and p=bst.n instead of from bst b and p=b.n?

Disallow

because you have set an alias for bst which is b so you have to use b for this table name – Duvall

Answer 1

The best way to write this code is to qualify all column references. So I would recommend:

SELECT b.N,
       (CASE WHEN b.P IS NULL
             THEN 'Root' 
             WHEN (SELECT COUNT(*) FROM BST b2 WHERE b2.P = b.N) > 0 
             THEN 'Inner'
             ELSE 'Leaf'
        END)
FROM bst b 
ORDER BY N;

This makes it clear that inner query is a correlated subquery, which is counting the number of times that a node in BST has the give node but not as a parent.

What are the conditions? Logically, these are:

CASE WHEN <there is no parent>
     WHEN <at least one node has this node as a parent>
     ELSE <not a parent and no nodes have this as a parent>
END

Note that I strongly discourage the use of COUNT(*) in correlated subquery to determine if there is any match. It is much better -- both from a performance perspective and a clearness perspective -- to use EXISTS:

SELECT b.N,
       (CASE WHEN b.P IS NULL
             THEN 'Root' 
             WHEN EXISTS (SELECT 1 FROM BST b2 WHERE b2.P = b.N) 
             THEN 'Inner'
             ELSE 'Leaf'
        END)
FROM bst b 
ORDER BY N;

Contortionist

What is b2 ? I understood b since your took the table bst aliased to b then what does b2 refer to? – Kelleykelli

The subquery aliases it to b2. – Contortionist

Answer 2

For getting Root Node P column value is null. For getting inner columns, P column value would be the ones which is not null but they may appear multiple times so a distinct on column values to get those and finally rest all of the nodes then would be Leaf node.

SELECT N, 
CASE 
   WHEN P IS NULL 
       THEN 'Root' 
   WHEN N IN (SELECT DISTINCT(P) FROM BST WHERE P IS NOT NULL) 
       THEN 'Inner' 
   ELSE 'Leaf' 
END 
FROM BST 
ORDER BY N;

Quarterdeck

Please add some explanation to your answer such that others can learn from it – Studley

For getting Root Node P column value is null. For getting inner columns, P column value would be the ones which is not null but they may appear multiple times so a distinct on column values to get those and finally rest all of the nodes then would be Leaf node. – Quarterdeck

Please add all explanation to your answer by editing it – Studley

Answer 3

On hackerrank , you can try just this if it helps :

select n,
case 
when p is null then 'Root'
when n in (select distinct(p) from bst) then 'Inner'
else 'Leaf'
end
from bst
order by n;

Phenolphthalein

Answer 4

You have two queries on bst. The main one and a sub-query with COUNT.

The sub query refers to its own result and to the one of the main query (b.N) in it’s WHERE part.

By removing the b alias, you also remove the possibility to reference to the main query from the sub query. And p=bst.n Is equal to p=n because bst is referring to the bst of the sub query and not the one of the main query.

Moleskin

why i need a alias to refence to the main query from the sub query ? – Disallow

@SaifAlSohad because both queries query bst so how should SELECT COUNT(*) FROM BST WHERE P = N know that P is of the own query but N is of its of the main query, both P and N are columns of bst, so N would in that case also the refer to the columns of the subquery. – Moleskin

Answer 5

SQL oracle:-

select n,(case when P is null then 'Root'
when N not in(select nvl(p,0) from bst) then 'Leaf'
else 'Inner' end) from bst order by n;

Phlegmy

worked in db2, could you explain a little more about nvl(p,0) – Kelleykelli

Answer 6

1.For SQLServer

    select distinct parent.N as Node
          ,(case when parent.p is null then "Root"
                 when parent.n is not null and child.p is null then 'Leaf'
              ELSE 'Inner'
          end ) as Node_type
     from BST as parent
    left join bst as child
    on parent.n = child.p
    order by parent.n

Tellurize

Answer 7

Use this:

SELECT N,
case 
when P IS NULL then 'Root'
when N in (select N from BST where N in 
(select P from BST where P  IS NOT 
NULL)) then 'Inner'
else 'Leaf'
end
FROM BST order by N

Sporocyst

While this code may solve the question, including an explanation of how and why this solves the problem would really help to improve the quality of your post, and probably result in more up-votes. Remember that you are answering the question for readers in the future, not just the person asking now. – Kerk

Answer 8

in sql server

with t1 as (
select n as rootnumber
    from bst
where p is null ),

t2 as (
select bst.n as innerorleaf,bst.p
from bst
    join t1 on bst.p=t1.rootnumber),
    
t3 as (
select bst.n as innerorleafalso,bst.p
from bst
join t2 on bst.p=t2.innerorleaf),

t4 as (
select bst.n as innerorleafalso2,bst.p
from bst
join t3 on bst.p=t3.innerorleafalso),

t5 as (
select bst.n as innerorleafalso3, bst.p
from bst
join t4 on bst.p=t4.innerorleafalso2),

t6 as (

SELECT rootnumber,"Root" as c2
FROM t1
UNION ALL
SELECT innerorleaf,"Inner" as c2
FROM t2
UNION ALL
SELECT innerorleafalso,"Inner" as c2
FROM t3
UNION ALL
SELECT innerorleafalso2,"Leaf" as c2
FROM t4)

SELECT * from t6 order by 1

Apoplectic

Pardon me, but I don't understand your answer. Are you offering an alternate query to achieve the same results as the query in the question? The OP is not asking for alternatives, (s)he wants an explanation as to why the query in the question produces the correct results. How does your answer provide that? – Tamper

Answer 9

Consider using CTE concept. Below inside the CTE I check the root & inner node using CASE statement, and outside (main) I identify the leaf nodes:

WITH sample as (select distinct
P.P pp,
case 
    when P.P = (select max(P) from BST) then 'Root' 
    when N.N < (select max(P) from BST) then 'Leaf' 
end root
from BST P inner join BST N on P.P = N.N)
select N, 
case
    when root is null then 'Leaf' 
    when root = 'Leaf' then 'Inner'
    when root = 'Root' then root
end final
from BST left join sample on BST.N = sample.pp
order by N

Armor

Here I am using the CTE concept, In CTE query I am checking the root & inner node using case statement and at main query identifying the leaf nodes. – Armor

Answer 10

SELECT BST.N,
CASE WHEN P IS NULL THEN 'Root'
WHEN BST.N in (SELECT DISTINCT BST.P FROM BST) THEN 'Inner'
ELSE 'Leaf'
END AS col_t
FROM BST
ORDER BY N;

Uncivilized

Please don't post only code as answer, but also provide an explanation what your code does and how it solves the problem of the question. Answers with an explanation are usually more helpful and of better quality, and are more likely to attract upvotes. – Tanbark