Search a node in array of children nodes in n-ary tree

Question

I'm stuck quith this issue from 2 weeks.

I have a basic treenode class in Python:

class Node:
    def __init__(self, data):
        self.data= data
        self.children = []
        self.parent = None

then I have a generic recursive search function:

def find_node(node, data):
    if node.data == data:
        return node

    if len(node.children)>0:
        for child in node.children:
            find_node(child, data)

I can't figure out why Python is searching only in the first occurrency of each "data" I pass to the find_node function.

I'm passing always the root node and then the string that identifies the node I'm looking for.

Really banging my head on the wall.

Answer 1

There are two problems in your code the first is that you are not returning the node if the function is called recursively. The second is that if you if you just use return find_node(child, data) the function will return on first pass but you only want to return if a node was found within the recursion function. Therefor you have to change

find_node(child, data)

with something like

potNode = find_node(child, data)
if not potNode is None:
    return potNode