Return or not return in a recursive function

Question

Before asking, I searched out some old questions and get a better idea to put the "return" in front of the inside re-invocated the function to get the expected result. some of them like: How to stop python recursion Python recursion and return statements. But when I do the same thing with my problem, it gets worse.

I have a Binary Search Tree and want to get the TreeNode instance by given a node's key, so it looks an easier traversal requirement and I already easily realized similar functions below, with which I did NOT put return in front of the function:

#preorder_List=[]
def preorder(treeNode):
    if treeNode:
        preorder_List.append(treeNode.getKey())
        preorder(treeNode.has_left_child())
        preorder(treeNode.has_right_child())
    return preorder_List

so for my new requirement, I compose it like below first:

def getNode(treeNode,key):
    if(treeNode):
        if(treeNode.key==key):
            print("got it=",treeNode.key)
            return treeNode
        else:
            getNode(treeNode.left_child(),key)    
            getNode(treeNode.right_child(),key)

then the issue occurs, it finds the key/node but kept running and report a None error finally and then I put return in front of the both left and right branch like below:

def getNode(treeNode,key):
    if(treeNode):
        if(treeNode.key==key):
            print("got it=",treeNode.key)
            return treeNode
        else:
            return getNode(treeNode.left_child(),key)    
            return getNode(treeNode.right_child(),key)   

but this makes the thing worse, it did reach the key found and return None earlier.

Then I tried to remove one "return" for the branch, no matter right or left. It works (Update: this worked when my test case contains only 3 nodes, when I put more nodes, it didn't work, or to say if the expected node is from right, then put return in front of right branch invocation works, for left one, it didn't). What's the better solution?

Answer 1

You need to be able to return the results of your recursive calls, but you don't always need to do so unconditionally. Sometimes you'll not get the result you need from the first recursion, so you need to recurse on the other one before returning anything.

The best way to deal with this is usually to assign the results of the recursion to a variable, which you can then test. So if getNode either returns a node (if it found the key), or None (if it didn't), you can do something like this:

result = getNode(treeNode.left_child(),key)    
if result is not None:
    return result
return getNode(treeNode.right_child(),key)

In this specific case, since None is falsey, you can use the or operator to do the "short-circuiting" for you:

return getNode(treeNode.left_child(),key) or getNode(treeNode.right_child(),key)

The second recursive call will only be made if the first one returned a falsey value (such as None).

Note that for some recursive algorithms, you may need to recurse multiple times unconditionally, then combine the results together before returning them. For instance, a function to add up the (numeric) key values in a tree might look something like this:

def sum_keys(node):
    if node is None:  # base case
        return 0
    left_sum = sumKeys(node.left_child())   # first recursion
    right_sum = sumKeys(node.right_child()) # second recursion
    return left_sum + right_sum + node.key  # add recursive results to our key and return

Answer 2

Without knowing more about your objects:

Three base cases:

• current node is None --> return None
• current node matches the key --> return it
• current node does not match, is the end of the branch --> return None

If not base case recurse. Short circuit the recursion with or: return the left branch if it a match or return the right branch result (which might also be None)

def getNode(treeNode,key):
    if treeNode == None:
        return None
    elif treeNode.key == key:
        print("got it=",treeNode.key)
        return treeNode
    elif not any(treeNode.has_left_child(), treeNode.has_right_child()):
        return None
    #left_branch = getNode(treeNode.left_child(),key)    
    #right_branch = getNode(treeNode.right_child(),key)
    #return left_branch or right_branch
    return getNode(treeNode.left_child(),key) or getNode(treeNode.right_child(),key)

Answer 3

Instead of return, use yield:

class Tree:
   def __init__(self, **kwargs):
      self.__dict__ = {i:kwargs.get(i) for i in ['left', 'key', 'right']}

t = Tree(key=10, right=Tree(key=20, left=Tree(key=18)), left=Tree(key=5))
def find_val(tree, target):
  if tree.key == target:
    yield target
    print('found')
  else:
    if getattr(tree, 'left', None) is not None:
      yield from find_val(tree.left, target)
    if getattr(tree, 'right', None) is not None:
      yield from find_val(tree.right, target)

print(list(find_val(t, 18)))

Output:

found
[18]

However, you could also implement the get_node function as a method in your binary tree class by implementing a __contains__ methods:

class Tree:
   def __init__(self, **kwargs):
     self.__dict__ = {i:kwargs.get(i) for i in ['left', 'key', 'right']} 
   def __contains__(self, _val):
     if self.key == _val:
        return True
     _l, _r = self.left, self.right
     return _val in [[], _l][bool(_l)] or _val in [[], _r][bool(_r)]

t = Tree(key=10, right=Tree(key=20, left=Tree(key=18)), left=Tree(key=5))
print({i:i in t for i in [10, 14, 18]})

Output:

{10: True, 14: False, 18: True}