CODEWITHSUNDEEP
pythonrecursiontreefindnodes
BamLess
BamLess

Reputation: 3

find and return a node from a tree in Python

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?

Upvotes: 0

Views: 4656

Answers (2)

blaze
blaze

Reputation: 2668

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)))

Upvotes: 1

Todd Tao
Todd Tao

Reputation: 41

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.

Upvotes: 1

Related Questions