I have created a BST table with two integer columns Node and Parent. I insert some values into this table and I want to detect leaf,inner and root node.
Code:
CREATE TABLE BST
(
Node int,
Parent int
);
INSERT INTO BST (Node, Parent) VALUES (1, 2);
INSERT INTO BST (Node, Parent) VALUES (3, 2);
INSERT INTO BST (Node, Parent) VALUES (6, 8);
INSERT INTO BST (Node, Parent) VALUES (9, 8);
INSERT INTO BST (Node, Parent) VALUES (2, 5);
INSERT INTO BST (Node, Parent) VALUES (8, 5);
INSERT INTO BST (Node) VALUES (5);
I write this query:
SELECT
Node,
CASE
WHEN Parent IS NULL THEN 'Root'
WHEN Node IS NOT NULL AND Parent IS NOT NULL
AND (SELECT Node FROM BST) NOT IN (SELECT Parent FROM BST)
THEN ('Leaf')
WHEN Node IS NOT NULL AND Parent IS NOT NULL
AND (SELECT Parent FROM BST) NOT IN (SELECT Node FROM BST)
THEN ('Inner')
END
FROM
BST;
And I was expecting to get a result like this:
1 Leaf
2 Inner
3 Leaf
5 Root
6 Leaf
8 Inner
9 Leaf
But I get this error:
Subquery returned more than 1 value. This is not permitted when the subquery follows =, !=, <, <= , >, >= or when the subquery is used as an expression.
Does anyone have any idea about this problem. Is this a syntax error or logical error? or my algorithm is not right...
As with my comment, this table design is poor for a BST. But it's not impossible, and we can get the desired answer (without needing a formal full traversal!) by using a lateral join from the table to itself:
SELECT p.Node, CASE WHEN p.Parent IS NULL THEN 'Root'
WHEN fc.Node IS NULL THEN 'Leaf'
ELSE 'Inner' END As NodeType
FROM BST p -- parent
OUTER APPLY (SELECT TOP 1 c.Node FROM BST c WHERE c.Parent = p.Node) fc -- first child
ORDER BY p.Node
It should also be possible to do this using a correlated subquery (and NOT EXISTS()) in the SELECT clause, but I find this much easier to write and reason about.
See it work here: