find and return a node from a tree in Python

Question

class WNode(object):
    def __init__(self,w):
        self._w=w
        self._content=[]
    def find(self, x):
        if self._w is x:
            return self
        else:
            for i in self._content:
                return i.find(x)
        return None

Hi. I'm having troubles to create a method tree.find(self,x) that returns the node with the name x in the tree if x is present (using recursion). The one that i wrote seems to be working only in certain cases(in simple trees with few levels) but in others(especially in larger trees) it returns None even if a node is present. Somebody knows how to create a working find(self,x) method that returns the x node?

@unixer i want to search the node x. So if it's equal to self._w (the name of the node) it returns the node itself otherwise the program search for a self._w that is equal to x recursively in every child node. But apparently it's not working — BamLess
– BamLess, Commented Nov 22, 2014 at 22:46
Please add the insertion method and the test case that is failing. — blaze
– blaze, Commented Nov 22, 2014 at 22:49
@blaze I use a function to create the tree. but it doesn't work even on simple tree like: r=WNode('1') r._content=[WNode('2'),WNode('3')]. if i type >>r.find('1') it returns the root node and same with the >>r.find('2'). But >>r.find('3')returns None even if a '3' node is present in r — BamLess
– BamLess, Commented Nov 22, 2014 at 23:01

Todd Tao · Accepted Answer · 2014-11-22 23:14:45Z

That's because your find function only looked for the node in the left-most branch. Thinking of an example of a tree as below:

      A
    /   \
   B     C
  / \
 D   E

Given that you are looking for the node C. Your find function looks branch B firstly, then checks D. D has no children so it ends the for loop and return None. It won't search the other branches as there has been something returned.

Actually if you wanna find a node in a tree, you should implement BFS or DFS algorithm to traverse your tree. Since your find function is DFS, I'll code DFS for you:

def find(self,x):
  s_list = []
  if self._w is x:
    return self
  else:
    s_list.extend(self._content)
    while s_list:
      node = s_list.pop()
      if node._w is x:
        return node
      else:
        s_list.extend(node._content)
  return None

s_list works as a search path which records every node find should check. If all the nodes has been checked then return None.

blaze · Accepted Answer · 2014-11-23 01:05:21Z

1

An alternative answer. Similar to yours and Todd Tao's solution, it implements a DFS. However, once it finishes exploring a branch unsuccessfully, it continues with the next one(s). Your code was searching just the left-most branch.

class WNode(object):

    def __init__(self,w):
        self._w=w
        self._content=[]

    def find(self, x):
        if self._w == x:
            return self
        else:
            y = None
            for i in self._content:
                y = i.find(x)
                if y:
                    break
            return y
        return None

if __name__ == '__main__':
    r = WNode(1)
    r._content = [WNode(2), WNode(3), WNode(4)]
    for i in xrange(1, 6):
        print('find({}) = {}'.format(i, r.find(i)))

edited Nov 23, 2014 at 1:05

answered Nov 22, 2014 at 23:26

blaze

2,6743 gold badges34 silver badges47 bronze badges

1 Comment

BamLess Over a year ago

this works if i create manually a tree, but it doesn't works on the tree generated by my function and i don't know why. i checked through a function that prints the trees but the manually created and the function created look just the same :S

Collectives™ on Stack Overflow

find and return a node from a tree in Python

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related