Looping through an “ancestral” dictionary

I am fairly new to coding but am working on a database project. I need to loop through a dictionary that is composed of ID’s and parent ID’s, seeing if anywhere down the line a given ID is related to specific ancestor. I am having trouble looping through the dictionary properly.

This is what I have so far. I built a small sample dictionary to test on

List = []

d = {
     1: 2,
     2: 3,
     3: 4,
     4: 5,
     7: 10,
     99: 3,
     26: 8,
     9: 26
}


for key in d:
    x = key
    y = d[x]
    for i in d:
        while y != 3:
            if i == y:
                y = d[i]
        List.append(x)
        
print(List)

the idea is to follow an id back to a given ancestor, and if it matches, add the original ID to a list.

Any help is appreciated and I am eager to learn, so an explanation of what/why would also be helpful! Thanks!

Answer

Are you “descended” from someone if that someone is yourself?

Obviously so.

Do you know who your father is?

If so, you are descended from someone if your father was descended from that person.

If not, then you cannot say you were descended from anyone.

Does all that make sense?

Let me write that in code:

def isDescendedFrom(child, forebearer, ancestry):
   # Are you “descended” from someone if that someone is *yourself*?
   if child == forebearer:
      #Obviously so.
      return True
   # Do you know who your father is?
   if child in ancestry:
     # If so, you are descended from someone 
     #   if your father was descended from that person.      
     return isDescendedFrom(ancestry[child], forebearer , ancestry)
   else:  
     # If not, then you cannot say you were descended from anyone.
     return False

See how that works?

You could re-write the above code as

def isDescendedFrom(child, forebearer, ancestry):
   return child == forebearer or 
       ((child in ancestry) and 
          isDescendedFrom(ancestry[child], forebearer , ancestry))

It might be less readable….

If you really wanted to win at CodeGolf:

def idf(c, p, a):
   return c and (c == p or idf(a.get(c), p, a))