I have below method where self contains a data structure as below

self.place = "India"
self.children = ["Tamil Nadu", "Karnataka"]
self.parent

Method

    def get_node(self, value):
        if value is None:
            return self

        if self.place == value:
            return self

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
               return node.get_node(value)

So via recursion, I am iterating on all possible child nodes to find the node I am looking for via return node.get_node(value) but I observed that, iteration happening via "Tamil Nadu" but not via "Karnataka".

I understood that, it took the first element of the list and then continued from there, but not coming back to 2nd element of the list.

is this expected behavior from recursion or am I doing something wrong ?

Full code( In case needed for testing)

class TreeNode:

    def __init__(self, place):
        self.place = place
        self.children = []
        self.parent = None

    def add_child(self, child):
        child.parent = self
        self.children.append(child)

    def print_tree(self):

        prefix = ""
        if self.parent is None:
            print(self.place)
        else:
            prefix = prefix   (" " * self.get_level() * 3)
            prefix = prefix   "|__"
            print(prefix   self.place)

        for child in self.children:
            child.print_tree()
    def get_level(self):
        level = 0
        p = self.parent
        while p:
            level = level   1
            p = p.parent
        return level

    def get_node(self, value):
        if value is None:
            return self

        if self.place == value:
            return self

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
               return node.get_node(value)

    def tree_map(self, nodes):
        for node in nodes:
            self.add_child(TreeNode(node))


def build_places():

    root = TreeNode("Global")

    india = TreeNode("India")
    usa = TreeNode("USA")

    root.add_child(india)
    root.add_child(usa)

    india_nodes = ["Gujarat" ,"Karnataka"]
    gujarath_nodes = [ "Ahmedabad", "Baroda"]
    karnataka_nodes = ["Bangalore", "Mysore"]
    usa_nodes = ["New Jersey", "California"]
    newjersey_nodes = ["Princeton", "Trenton"]
    california_nodes = ["San Franciso", "Mountain View", "Palo Alto"]

    for node in india_nodes:
        india.add_child(TreeNode(node))
    for node in usa_nodes:
        usa.add_child(TreeNode(node))

    gujarath_node = root.get_node("Gujarat")
    print(gujarath_node.place)
    for node in gujarath_nodes:
        gujarath_node.add_child(TreeNode(node))
    karnataka_node = root.get_node("Karnataka")
    print(karnataka_node.place)
    return root


if __name__ == "__main__":
    root = build_places()
    root.print_tree()

CodePudding user response：

The problem is that in your loop you are always exiting the loop in its first iteration (when the node has at least some children). You should only exit on success, not when the recursive call comes back without success.

So change the loop to this:

        for node in self.children:
            if node.place == value:
                return node
            elif len(node.children) > 0:
                result = node.get_node(value)
                if result:
                    return result

Secondly, there is a strange base case you have at the start of this function. I would replace this:

        if value is None:
            return self

With:

        if value is None:
            return None

...since you didn't look for the value in that case: so then (in my opinion) it is not right to return a node instance (which might have any value -- you didn't verify it). It seems more consistent to return None or to remove this whole if block and not treat None in a special way.