SQL Server 2022

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
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);
7 rows affected

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


Node
NodeType


1
Leaf

2
Inner

3
Leaf

5
Root

6
Leaf

8
Inner

9
Leaf


SELECT Node, CASE WHEN Parent IS NULL THEN 'Root'
                  WHEN NOT EXISTS (SELECT 1 FROM BST c WHERE c.Parent = p.Node) THEN 'Leaf'
                  ELSE 'Inner' END As NodeType
FROM BST p
ORDER BY Node


Node
NodeType


1
Leaf

2
Inner

3
Leaf

5
Root

6
Leaf

8
Inner

9
Leaf