Finding ultimate parent-id child relationship using pyspark or python

Hello everyone, hope you are enjoying the weekend? Please I need your help on this:

I am trying to find the ultimate parentId of all the descendants and children (parent,grand child) using spark sql or python on Azure spark pool(Serverless pool) But the task has one specialty where the recursive doesn't work. So, I need a customed code to get the root and all the children. The dept of the tree or table is not known. Below is my sample data table.

DECLARE @TestDataProj TABLE (
projid VARCHAR(30), ProjName VARCHAR(255), Parentid VARCHAR(30)
)
INSERT INTO @TestDataProj
VALUES ('1001', 'A', '8888')
INSERT INTO @TestDataProj
VALUES ('1001', 'D', '1002')
INSERT INTO @TestDataProj
VALUES ('1001', 'C', '1002')
INSERT INTO @TestDataProj
VALUES ('1001', 'C', '1003')
INSERT INTO @TestDataProj
VALUES ('1003', 'G', '6666')
INSERT INTO @TestDataProj
VALUES ('1002', 'H', '9999')

Select * from @TestDataProj

My desired output should be like this:

DECLARE @DesiredTestResult TABLE (
projid VARCHAR(30),ProjName VARCHAR(255),Parentid VARCHAR(30),
UltimateParentid VARCHAR(30)
)
INSERT INTO @DesiredTestResult
VALUES ('1001', 'A', '8888','8888')
INSERT INTO @DesiredTestResult
VALUES ('1001', 'D', '1002','9999')
INSERT INTO @DesiredTestResult
VALUES ('1001', 'C', '1002','9999')
INSERT INTO @DesiredTestResult
VALUES ('1001', 'C', '1003','6666')
INSERT INTO @DesiredTestResult
VALUES ('1003', 'G', '6666','6666')
INSERT INTO @DesiredTestResult
VALUES ('1002', 'H', '9999','9999')
Select * from @DesiredTestResult

Thanking you in advance

Libby