CODEWITHSUNDEEP
pythonrecursiontree
user2650946
user2650946

Reputation: 41

Finding a node in a tree

I am having trouble finding a node in a tree with arbitrary branching factor. Each Node carries data and has zero or greater children. The search method is inside the Node class and checks to see if that Node carries data and then checks all of that Nodes children. I keep ending up with infinite loops in my recursive method, any help?

def find(self, x):

    _level = [self]
    _nextlevel = []

    if _level == []: 
        return None
    else:
        for node in _level:
            if node.data is x:
                return node
            _nextlevel += node.children
        _level = _nextlevel
    return self.find(x) + _level

The find method is in the Node class and checks if data x is in the node the method is called from, then checks all of that nodes children. I keep getting an infinite loop, really stuck at this point any insight would be appreciated.

Upvotes: 1

Views: 1351

Answers (2)

theodox
theodox

Reputation: 12208

A simple pattern for recursive searches is to use a generator. That makes it easy to pass up the answers to calling code without managing the state of the recursion yourself.

class Example(object):
     def __init__(self, datum,  *children):
         self.Children = list(children) # < assumed to be of the same or duck-similar class
         self.Datum = datum

     def GetChildren(self):
         for item in self.Children: 
             for subitem in item.GetChildren():
                 yield subitem
             yield item

     def FindInChildren(self, query):  # where query is an expression that is true for desired data
         for item in self.GetChildren():
             if query(item):
                yield item

Upvotes: 1

Oliver Dain
Oliver Dain

Reputation: 9953

There are a few issues with this code. First, note that on line 2 you have _level = [self]. that means the if _level == [] on line 5 will always be false.

The 2nd issue is that your for loop goes over everything in _level, but, as noted above, that will always be [self] due to line 2.

The 3rd issue is the return statement. You have return self.find(x) + _level. That gets evaluated in 2 parts. First, call self.find(x), then concatenate what that returns with the contents of _level. But, when you call self.find(x) that will call the same method with the same arguments and that, in turn, will then hit the same return self.find(x) + _level line, which will call the same method again, and on and on forever.

Upvotes: 1

Related Questions