depth first tree search

Question

I'm having trouble implementing a recursive depth-first search on a tree structure in python 2.7, could anyone point me in the right direction?

Code

class node(object):
    def __init__(self, value,children=[]):
        self.value=value
        self.children=children
    def __repr__ (self,level=0):
        ret = "\t"*level+repr(self.value)+"\n"
        for child in self.children:
            ret +=child.__repr__(level+1)
        return ret  

    def search(self,st):
        if self.value==st:
            return True
        else:
            if not self.children:
                return False
            else:               
                for child in self.children:
                    self.search(st)

sample data structure (for simple pasting):

tree = node("fashion",[
    node("garment",[
        node("t-shirt"),
        node("shorts")]),
    node("designer",[
        node("Ralf"),
        node("tommy"),
        node("joe")])
    ])

EDIT: the problem is that I'm ending in an infinate loop when searching, for example:

tree.search("garment")

EDIT 2: update to fix the recursion not advancing (thanks Ben!), but not getting a False answer to tree.search("joe")

    def search(self,st):
    if self.value==st:
        return True
    else:
        if self.children:
            for child in self.children:
                return child.search(st)             
        else:               
            return False

EDIT 3: astute observations from Sharth have led me to

def search(self,st):
    if self.value==st:
        return True
    for child in self.children:
        if child.search(st):
            return True         
    return False

Which works great, but searching

>>>tree.search("p")

produces

Traceback (most recent call last): File "", line 1, in tree.search("p") File "", line 15, in search if child.search(st): AttributeError: 'list' object has no attribute 'search'

why is that happening?

EDIT4: works when using the above data structure, but fails with a third level of data, i.e.

tree = node("fashion",[
    node("garment",[
        node("t-shirt"),
        node("shorts")]),
    node("designer",[
        node("Ralf"),
        node("tommy"),
        node("joe"),[
        node("fresh")]
    ])
    ])

edit 5: messed up the braces in edit four.

Answer 1

In the following code, 3 issues have been fixed:

1. Mutable default arguments
2. When looping, we need to call child.search(st), not self.search(st).
3. We don't want to only look at the first child (as your 2nd edit does), we want to return success on the first one that is true. If the first one is false, we want to try the next..

So, the code:

class node(object):
    def __init__(self, value, children=None):
        self.value = value
        self.children = children or []

    def search(self, st):
        if self.value == st:
            return True
        for child in self.children:
             if child.search(st):
                 return True
        return False

Answer 2

It looks like your search function isn't actually searching the children. Try this instead:

def search(self,st):
    if self.value==st:
        return True
    else:
        if not self.children:
            return False
        else:               
            return any(child.search(st) for child in self.children)

Notice that the last line has been modified to use a generator expression in conjunction with the built-in function any in order to search each of the children in sequence, stopping as soon as one of them results in a True.

The key difference here is that we call child.search(st) instead of self.search(st).

Also note that you really don't need a separate case for when children is empty, so you could do this instead:

def search(self,st):
    if self.value==st:
        return True
    else:
        return any(child.search(st) for child in self.children)

This can be further simplified:

def search(self,st):
    return self.value==st or any(child.search(st) for child in self.children)

When you're returning a boolean literal it's a good sign that you can probably simplify by using and / or instead.

Answer 3

Please set children to None and not a list. Its very dangerous to have a mutable argument as a default parameter. See Hidden features of Python for reference. The value of children may not be an empty list, even if its intended to be.