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?

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;

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;

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;

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.

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;

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

Answer 7

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;