python - depth first tree seach -

python - depth first tree seach -

i'm having problem implementing recursive depth-first search on tree structure in python 2.7, point me in 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" kid in self.children: ret +=child.__repr__(level+1) homecoming ret def search(self,st): if self.value==st: homecoming true else: if not self.children: homecoming false else: kid in self.children: self.search(st)

sample info construction (for simple pasting):

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

edit: problem i'm ending in infinate loop when searching, example:

tree.search("garment")

edit 2: update prepare recursion not advancing (thanks ben!), not getting false reply tree.search("joe")

def search(self,st): if self.value==st: homecoming true else: if self.children: kid in self.children: homecoming child.search(st) else: homecoming false

edit 3: astute observations sharth have led me

def search(self,st): if self.value==st: homecoming true kid in self.children: if child.search(st): homecoming true homecoming false

which works great, searching

>>>tree.search("p")

produces

traceback (most recent phone 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 happening?

edit4: works when using above info structure, fails 3rd 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 braces in edit four. dummy. help!!

in next code, 3 issues have been fixed:

mutable default arguments when looping, need phone call child.search(st), not self.search(st). we don't want @ first kid (as 2nd edit does), want homecoming success on first 1 true. if first 1 false, want seek next..

so, 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: homecoming true kid in self.children: if child.search(st): homecoming true homecoming false

python python-2.7