Problem in Graph and Tree question in Python

Question

I want to solve a Question in Tree and Graph problem and i write code for this problem but this gives me wrong answer but i think code? Please Help me out🙏.

class Graph:
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
    
    def addEdge(self, vertex, edge):
        self.gdict[vertex].append(edge)
    
    def checkRoute(self, startNode, endNode):
        for key in self.gdict.keys():
            if key == startNode:
                if endNode in self.gdict[key]:
                    print(self.gdict[key])
                    return "True"
                else:
                    for j in self.gdict[key]:
                        self.checkRoute(j, endNode)
        return "False"

This is the input.

`customdict = {"a": ['c', 'd', 'b'],
        "b": ['j'],
        "c": ['g'],
        'd': [],
        'e': ['f', 'a'],
        "f": ['i'],
        'g': ['d', 'h'],
        "h": [],
        "i": [],
        "j": []} 

g = Graph(customdict)
print(g.checkRoute("a", "j"))

`

This gives me output

['j'] False

When my code enter in this block

if endNode in self.gdict[key]:
     print(self.gdict[key])
       return "True"

so I want to this gives me answer

True

but this gives me :

False,

Answer 1

The main issue is that the result of your recursive call is ignored. If the recursive call successfully finds the end node, then that loop should not continue. Instead you should propagate the positive result to the caller.

But there are also the following remarks:

• The function should not return a string, but a boolean, so False or True, not "False" or "True"

• The outer loop is not needed. You don't have to iterate a dictionary to find a particular key. Use the in operator instead and keep working with startNode as there is no need to have key as variable.

• When start node and end node are equal, then the function should never return False. Yet it will do so for some nodes, like "e". This is because it currently requires the path to have at least one edge. So put the equality test outside any loop.

Here is the corrected function:

    def checkRoute(self, startNode, endNode):
        if startNode not in self.gdict:  # Don't iterate, just check
            return False  # Non-existing node
        if startNode == endNode:  # Success should be checked on startNode
            return True
        for neighbor in self.gdict[startNode]:
            if self.checkRoute(neighbor, endNode):
                return True  # Success: exit!
        return False