Return more than one int value

Question

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...

Answer 1

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:

https://dbfiddle.uk/wNFbOdl4

Answer 2

I assume you're looking for Recursive CTE in sql server? Your query is not working because you cannot call query itself within a subquery. I just add a roughly thought here, if you'd like to learn more about Recursive CTE, please review msdn https://learn.microsoft.com/en-us/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver16

WITH Root AS (
  SELECT
    Node,
    1 AS level
  FROM BST
  WHERE parent IS NULL
  UNION ALL
  SELECT
    b.parent,
    level + 1
  FROM BST b
  INNER JOIN Root r
    ON b.Parent = r.Node
)
SELECT *
FROM Root;

Answer 3

If you no need recursive query for tree traversal, you can use this query (in your initial style, but OUTER APPLY option better for my taste =):

select node,
        case
            when Parent IS NULL then 'Root'
            when not exists(select * from bst sub where sub.parent = r.node) then 'Leaf'
            else 'Inner'
        end type
    from bst r

Here you no need special conditions for "Inner" items - they are just not Root and not Leaf. And Leaf you can check if it's has no one child.

Answer 4

The initial problem is with your AND (SELECT Node_ FROM BST) NOT IN (SELECT Parent FROM BST) condition. The left side needs to be a single value, and it appears that you intended to reference the Node column value from the current main FROM BST row. In that case, you would need something like AND Node NOT IN (SELECT Parent FROM BST).

The next WHEN case is similar, but at that point, I think all you need is ELSE 'Inner'.

There is also an issue with NOT IN (subselect). If the subselect yields any null values, the NOT IN condition will effectively be false, even if some other value matches. This can be fixed by adding a NOT NULL filter to the subselect - AND Node NOT IN (SELECT Parent FROM BST WHERE Parent IS NOT NULL), but it might be better to use a NOT EXISTS() as in NOT EXISTS (SELECT * FROM BST C WHERE C.Parent = B.Node) (with table aliases).

Adding aliases to all of your table references and qualifying all column references with those aliases is best practice, especially with subselects.

The Node IS NOT NULL AND Parent IS NOT NULL part of the condition is unnecessary and can be removed.

The result would be something like:

SELECT
    B.Node,
    CASE
        WHEN B.Parent IS NULL
            THEN 'Root'
        WHEN NOT EXISTS (SELECT * FROM BST C WHERE C.Parent = B.Node) 
            THEN 'Leaf'
        ELSE 'Inner'
    END
FROM
    BST B
ORDER BY
    B.Node;

See this db<>fiddle.

Answer 5

I edited my code to:

select Node_ as Nodes,
  case
    when Parent is null then 'Root'
    when Node_ is not null 
         and Parent is not null 
         and Node_ in (select Parent from BST) 
         then ('Inner')
    else ('Leaf')
  end NodeType
from BST

And it worked! Is there any exception that will cause problem in other cases in my code?