Postgres 14

By using db<>fiddle, you agree to license everything you submit by Creative Commons CC0.
-- your table
CREATE TABLE tbl ("EmployeePositionId" int, "Subdivision" int, "Parent" int);
INSERT INTO tbl VALUES
  (   1,   42, NULL)
, (4718,  485,   42)
, (4719, 5064,  485)
, (4720, 5065, 5064)
, (4721, 5065, 5064)
, (4722, 3000, NULL)

, (   2,   43, NULL)
, (6718, 8485,   43)
, (6719, 8064, 8485)
, (6720, 8065, 8064)
, (6721, 8065, 8064)
, (6722, 7000, NULL)
;

CREATE TABLE



INSERT 0 12


-- materialized view with added level + indexes
CREATE MATERIALIZED VIEW mv_tbl AS
WITH RECURSIVE cte AS (
   SELECT *, 0 AS level
   FROM   tbl
   WHERE  "Parent" IS NULL
   
   UNION ALL
   SELECT t.*, c.level + 1
   FROM   cte c
   JOIN   tbl t ON t."Parent" = c."Subdivision"
   )
TABLE cte;

-- tailored indexes
CREATE UNIQUE INDEX mv_tbl_id_uni ON mv_tbl ("EmployeePositionId") INCLUDE ("Subdivision", "Parent", level);
CREATE INDEX  mv_tbl_subdivision_idx ON mv_tbl ("Subdivision") INCLUDE ("Parent", level);

SELECT 12



CREATE INDEX



CREATE INDEX


-- updated setup with guarantee of NULL termination and added level:
WITH RECURSIVE init AS (
   SELECT "Subdivision", "Parent", level
   FROM   mv_tbl
   WHERE  "EmployeePositionId" IN (4719, 4720, 4721)  -- input
   )
, cte AS (
   TABLE init
   UNION
   SELECT c."Parent", t."Parent", c.level - 1
   FROM   cte c
   JOIN   mv_tbl t ON t."Subdivision" = c."Parent"  -- recursion terminated at "Parent" IS NULL
   )
, agg AS (
   SELECT level, min("Subdivision") AS "Subdivision", count(*) AS ct
   FROM   cte
   GROUP  BY  level
   )
SELECT "Subdivision"
FROM   agg a
WHERE  ct = 1                                  -- no other live branch
AND    level <  (SELECT max(level) FROM cte WHERE "Parent" IS NULL) IS NOT TRUE  -- no earlier dead end
AND    level <= (SELECT min(level) FROM init)  -- include highest (least) level
ORDER  BY level DESC                           -- pick earliest (greatest) qualifying level
LIMIT  1;


Subdivision


5064



SELECT 1


-- with your original setup: no reliable NULL termination
WITH RECURSIVE init AS (
   SELECT "Subdivision", "Parent", level
   FROM   mv_tbl
   WHERE  "EmployeePositionId" IN (4719, 4720, 4721)  -- input
   )
, cte AS (
   TABLE init
   UNION
   SELECT c."Parent", t."Parent", c.level - 1
   FROM   cte c
   LEFT   JOIN mv_tbl t ON t."Subdivision" = c."Parent"  -- terminate recursion with NULL row  !!
   WHERE  c."Parent" IS NOT NULL
   )
, agg AS (
   SELECT level, min("Subdivision") AS "Subdivision", count(*) AS ct
   FROM   cte
   GROUP  BY  level
   )
SELECT "Subdivision"
FROM   agg a
WHERE  ct = 1                                  -- no other live branch
AND    level <  (SELECT max(level) FROM cte WHERE "Parent" IS NULL) IS NOT TRUE  -- no earlier dead end
AND    level <= (SELECT min(level) FROM init)  -- include highest (least) level
ORDER  BY level DESC                           -- pick earliest (greatest) qualifying level
LIMIT  1;


Subdivision


5064



SELECT 1


-- no common parent, no result:
WITH RECURSIVE init AS (
   SELECT "Subdivision", "Parent", level
   FROM   mv_tbl
   WHERE  "EmployeePositionId" IN (4719, 4720, 4721, 4722)  -- input
   )
, cte AS (
   TABLE init
   UNION
   SELECT c."Parent", t."Parent", c.level - 1
   FROM   cte c
   JOIN   mv_tbl t ON t."Subdivision" = c."Parent"  -- recursion terminated at "Parent" IS NULL
   )
, agg AS (
   SELECT level, min("Subdivision") AS "Subdivision", count(*) AS ct
   FROM   cte
   GROUP  BY  level
   )
SELECT "Subdivision"
FROM   agg a
WHERE  ct = 1                                  -- no other live branch
AND    level <  (SELECT max(level) FROM cte WHERE "Parent" IS NULL) IS NOT TRUE  -- no earlier dead end
AND    level <= (SELECT min(level) FROM init)  -- include highest (least) level
ORDER  BY level DESC                           -- pick earliest (greatest) qualifying level
LIMIT  1;


Subdivision



SELECT 0