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

Issue

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?

Solution

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;

Answered By – Gordon Linoff

This Answer collected from stackoverflow, is licensed under cc by-sa 2.5 , cc by-sa 3.0 and cc by-sa 4.0

Leave a Reply

(*) Required, Your email will not be published