How to return value from recursive function in python?
<p>I'm working with binary tree in python. I need to create a method which searches the tree and return the best node where a new value can be inserted. But i'm have trouble returning a value from this recursive function. I'm a total newbie in python.</p>

<pre><code>def return_key(self, val, node):
    if(val &lt; node.v):
        if(node.l != None):
            self.return_key(val, node.l)
        else:
            print node.v
            return node
    else:
        if(node.r != None):
            #print node.v
            self.return_key(val, node.r)
        else:
            print node.v
            return node
</code></pre>

<p>Printing <code>node.v</code> prints the node value, but when i print the returned node :</p>

<pre><code>print ((tree.return_key(6, tree.getRoot().v)))
</code></pre>

<p>it prints</p>

<blockquote>
  <p>None </p>
</blockquote>

<p>as result.</p>

<p>You need to return the result of your <em>recursive</em> call. You are ignoring it here:</p>

<pre><code>if(node.l != None):
    self.return_key(val, node.l)
</code></pre>

<p>and</p>

<pre><code>if(node.r != None):
    self.return_key(val, node.r)
</code></pre>

<p>Recursive calls are no different from other function calls, you still need to handle the return value if there is one. Use a <code>return</code> statement:</p>

<pre><code>if(node.l != None):
    return self.return_key(val, node.l)

# ...

if(node.r != None):
    return self.return_key(val, node.r)
</code></pre>

<p>Note that since <code>None</code> is a singleton value, you can and should use <code>is not None</code> here to test for the absence:</p>

<pre><code>if node.l is not None:
    return self.return_key(val, node.l)

# ...

if node.r is not None:
    return self.return_key(val, node.r)
</code></pre>

<p>I suspect you are passing in the wrong arguments to the call to begin with however; if the second argument is to be a node, don't pass in the node value:</p>

<pre><code>print(tree.return_key(6, tree.getRoot())) # drop the .v
</code></pre>

<p>Also, if all your <code>node</code> classes have the same method, you could recurse to that rather than using <code>self.return_value()</code>; on the <code>Tree</code> just do:</p>

<pre><code>print tree.return_key(6)
</code></pre>

<p>where <code>Tree.return_key()</code> delegates to the root node:</p>

<pre><code>def return_key(self, val):
    root = tree.getRoot()
    if root is not None:
        return tree.getRoot().return_key(val)
</code></pre>

<p>and <code>Node.return_key()</code> becomes:</p>

<pre><code>def return_key(self, val):
    if val &lt; self.v:
        if self.l is not None:
            return self.l.return_key(val)
    elif val &gt; self.v:
        if self.r is not None:
            return self.r.return_key(val)

    # val == self.v or child node is None
    return self
</code></pre>

<p>I updated the <code>val</code> testing logic here too; if <code>val &lt; self.v</code> (or <code>val &lt; node.v</code> in your code) is false, <em>don't</em> assume that <code>val &gt; self.v</code> is true; <code>val</code> could be equal instead.</p>

python python-2.7 python-3.x recursion binary-search-tree