Search function for a n-ary tree using python

Question

I am trying to build a search function for the n-ary tree. Here is how node class is :

class node(object):
  """docstring for node"""
  def __init__(self, val=''):
    self.val = val #value of the node
    self.subtrees = [] #list of subtree node objects

following is the code how I call search function:

temp_search(root, "1")

And there is one node whose value is "1". And I expect node object to be returned on successful search.

following is my first search function I implemented:

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

The above thing returns 'None' and it never printed 'Found'

Now I modified it a bit:

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

Though it returns 'None' it still printed 'Found'. Okay thats some improvement.

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:

#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

Similarly I implemented multi search like this [i.e. it should return all nodes whose value matches to key]

#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

I would call above function like this:

temp_multi_search(root, "1")

But I got result as :

[<__main__.node object at 0x101eb4610>, [...], [...], [...], [...], [...], [...], [...], <__main__.node object at 0x101eb47d0>, [...], [...], [...], [...]]

So it was appending empty lists(?). This is how I fixed it:

#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

Now I would get correct, expected result :

[<__main__.node object at 0x10b697610>, <__main__.node object at 0x10b6977d0>]

Here are my questions :

1. 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?
2. 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?
3. Have I implemented temp_search v0.3 in a right way? Any improvements?
4. Why temp_multi_search v0.1 is failing?
5. Have I implemented temp_multi_search v0.2 in a right way? Any improvements?

Here is what I think:

1. 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
2. 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
3. -
4. I think it is failing because the return temp would be some list, so it is just appending it to result.
5. -

Answer 1

1. Your answer is correct. Since the function call on first subtree always returns (regardless the value is found or not), it won't check for next subtrees.
2. You don't have return statement, so at the end of the function Python will implicitly insert return None
3. This is already optimal. There is no single Python statement that can do that.
4. The lists (not empty list!) are added because you do return result, and so the parent function call will receive a list (of results) as the result. Then it will append to its local copy of result, and return.
5. You can improve this by not giving result as a parameter:

#temp_multi_search v0.25
def temp_multi_search(some_node, key):
    result = []                    # Line 1
    if some_node.val == key:
        print 'found', some_node
        result.append(some_node)   # Line 2
    for subtree in some_node.subtrees:         
        result.extend(temp_multi_search(subtree, key)) # Line 3
    return result

Explanation:

It will first check the value on the root node, if it doesn't match, we don't append that node to the search result, otherwise, we add that to our result so far (which would only contain itself). Next we check every subtree.

Now, we already know that the function temp_multi_search(subtree, key) will return all occurrences on that tree. So after we call temp_multi_search(subtree, key) on each child, we extend the result found in that subtree to our result so far (which might have included the results from previous children).

At the end of iterating all children, we return our result.

Example:

Suppose we are looking for the number 1 in the following tree, and expects the function to return all occurrences.

          0
   _______|________
   |      |       |
   1      2       3
  _|_    _|_   ___|___
  | |    | |   |  |  |
  1 4    1 5   6  1  7

So first we call temp_multi_search(root,1). It's not 1, so result is still empty now.

Next we check each subtree:

1. Child 1: The node value matches, so we add it into the result (at Line 2). Now say we have result = [node1]. Then check each subtree:
   • GrandChild 1: The node value matches, so we add it into the result (at Line 2). No more subtrees. Return [node2]. The Child 1 call will extend the result [node2] into his result [node1] (Line 3). So the Child 1 now has [node1, node2].
   • GrandChild 2: Node value doesn't match. No more subtrees. Return []. Child 1 extend empty list, so no change.
2. Child 2: Doesn't match. Check each subtree:
   • GrandChild 3: Match. Add to result (Line 2). No more subtrees. Return [node5]. Child 2 becomes [node5] (Line 3).
   • GrandChild 4: Doesn't match. No more subtrees. Return []. Child 2 still [node5].
3. Child 3: Doesn't match. Check each subtree:
   • GrandChild 5: Doesn't match. No more subtrees. Return []
   • GrandChild 6: Match Add to result (Line 2). Return [node9]. Child 3 will extend it to be [node9] (Line 3)
   • GrandChild 7: Doesn't match. No more subtrees. Return [].

At the end of each mentioned step, the returned result will be extended to Root result by Line 3. So after Step 1, Root result is [node1, node2]. After Step 2, Root result is [node1, node2, node5]. After Step 3, Root result is [node1, node2, node5, node9].

Then after checking all children, return the result.