title: Search function for a n-ary tree using python
body: <p>I am trying to build a search function for the n-ary tree. Here is how node class is :</p>
  
  <pre><code>class node(object):
    """docstring for node"""
    def __init__(self, val=''):
      self.val = val #value of the node
      self.subtrees = [] #list of subtree node objects
  </code></pre>
  
  <p>following is the code how I call search function:</p>
  
  <pre><code>temp_search(root, "1")
  </code></pre>
  
  <p>And there is one node whose value is "1". And I expect node object to be returned on successful search. </p>
  
  <p>following is my first search function I implemented:</p>
  
  <pre><code>#temp_search v0.1
  def temp_search(node, key):
      if node.val == key:
          print 'Found', node
          return node
      for subtree in node.subtrees:         
          return temp_search(subtree, key)
  </code></pre>
  
  <p>The above thing returns 'None' and it never printed 'Found'</p>
  
  <p>Now I modified it a bit:</p>
  
  <pre><code>#temp_search v0.2
  def temp_search(node, key):
      if node.val == key:
          print 'found', node
          return node
      for subtree in node.subtrees:         
          temp_search(subtree, key)  
  </code></pre>
  
  <p>Though it returns 'None' it still printed 'Found'. Okay thats some improvement. </p>
  
  <p>So I realized that loop is running on each subtree object even after it returned the node. Does that make any sense? Because I think once it returned something, it should come out of it right? So modified it again:</p>
  
  <pre><code>#temp_search v0.3
  def temp_search(node, key):
      if node.val == key:
          print 'Found', node
          return node       
      for subtree in node.subtrees:         
          temp = temp_search(subtree, key)
          if temp:
              return temp
  </code></pre>
  
  <p>Similarly I implemented multi search like this [i.e. it should return all nodes whose value matches to key]</p>
  
  <pre><code>#temp_multi_search v0.1
  def temp_multi_search(some_node, key, result=[]):
      if some_node.val == key:
          print 'found', some_node
          return result.append(some_node)
      for subtree in some_node.subtrees:         
          temp = temp_multi_search(subtree, key, result)
          if temp:
              result.append(temp)
      return result
  </code></pre>
  
  <p>I would call above function like this:</p>
  
  <pre><code>temp_multi_search(root, "1")
  </code></pre>
  
  <p>But I got result as :</p>
  
  <p><code>[&lt;__main__.node object at 0x101eb4610&gt;, [...], [...], [...], [...], [...], [...], [...], &lt;__main__.node object at 0x101eb47d0&gt;, [...], [...], [...], [...]]</code></p>
  
  <p>So it was appending empty lists(?). This is how I fixed it:</p>
  
  <pre><code>#temp_multi_search v0.2
  def temp_multi_search(some_node, key, result=[]):
      #result = []
      if some_node.val == key:
          print 'found', some_node
          return result.append(some_node)
      for subtree in some_node.subtrees:         
          temp = temp_multi_search(subtree, key, result)
          if isinstance(temp, node):
               result.append(temp)
      return result
  </code></pre>
  
  <p>Now I would get correct, expected result :</p>
  
  <pre><code>[&lt;__main__.node object at 0x10b697610&gt;, &lt;__main__.node object at 0x10b6977d0&gt;]
  </code></pre>
  
  <p>Here are my questions :</p>
  
  <ol>
  <li>Why temp_search v0.1 failing? When going to through each subtree, when the search result is found, the value is returned. Why the loop is not getting terminated?</li>
  <li>In temp_search v0.2, I don't have return statement in for loop. So what difference here it is making? Since the object is being found, but how do I return it successfully?</li>
  <li>Have I implemented temp_search v0.3 in a right way? Any improvements?</li>
  <li>Why temp_multi_search v0.1 is failing?</li>
  <li>Have I implemented temp_multi_search v0.2 in a right way? Any improvements?</li>
  </ol>
  
  <p>Here is what I think:</p>
  
  <ol>
  <li>I think the for loop is running is only once. It searches in the first subtree only (recursively), which returns if item not present it returns none. I confirmed this via sending a value which was present in first subtree</li>
  <li>Here for loop is successfully running on each subtree, thats why it is able to find the node. But how do I make it return the node other method than temp_search v0.3? I find temp_search v0.3 less pythonic</li>
  <li>-</li>
  <li>I think it is failing because the return temp would be some list, so it is just appending it to result.</li>
  <li>-</li>
  </ol>