Bubbling up return values from recursive call in Python

Question

I'm unfamiliar with how to bubble up a return call from a recursive function call in Python. In this example I'm writing a 'check if something is a binary tree method' which has to return true or false. However if I call it from another function (even when I hit my conditional) I will not get False returned.

How can I ensure that this return call goes all the way up?

def isValidTree(root, tempArr):
    if(root.left):
        return isValidTree(root.left, tempArr)

    if(len(tempArr) == 0):
        tempArr.append(root.data)
    elif(tempArr[len(tempArr) - 1] >= root.data):
        return False
    else:
        tempArr.append(root.data)

    if(root.right):
        return isValidTree(root.right, tempArr)

def isBinarySearchTree(root):
    print(isValidTree(root, []))

Part A : In your if case, you are returning None ( albeit implicitly) in two cases. Part B : What do you want this tempArr to do. If this happens to be a binary array fetch all the leaf values ? — Vasif, May 25 '17 at 23:31
Also, you are returning 'False' as a string. Which is a truthy value. Try returning False as a keyword. — Vasif, May 25 '17 at 23:33
@Vasif should I therefor be explicitly returning something in my if case? The temp array is adding each leaf of the tree (via in order traversal), then checking to see if the previous value in the array is in the proper order. ie a proper BST with values 1,2,3,4,5 should be in that order. — Xelad1, May 26 '17 at 00:36
There is currently no `True` execution path, so if `isValidTree()` returns any value it will be `False`. You need to work out how your function will terminate successfully. When indexing, you can also use negative indices, so `tempArr[-1]` is the last element — import random, May 26 '17 at 05:04

score 1 · Answer 1 · answered May 26 '17 at 00:41

Rather than just returning the result of the recursive call to isValidTree(root.left) and isValidTree(root.right), you should check if the recursive calls return False, and in that case propagate the False result to the caller. Furthermore, you should return True if no error is encountered:

def isValidTree(root, tempArr):
    if root.left:
        if not isValidTree(root.left, tempArr):
            # Propagate error in left subtree to the parent.
            return False

    if len(tempArr) == 0:
        tempArr.append(root.data)
    elif tempArr[len(tempArr) - 1] >= root.data:
        return False
    else:
        tempArr.append(root.data)

    if root.right:
        if not isValidTree(root.right, tempArr):
            # Propagate error in right subtree to the parent.
            return False

    # No errors encountered, so it was valid.
    return True

score 1 · Answer 2 · answered May 26 '17 at 00:59

The way your code is structured when you traverse the tree the value that should be returned, True or False to indicate the validity of the subtree, is not done. As @Vasif indicated you are returning a string or None which is not what you want.

You need to test for the base condition first which is Am I at a leaf?

I am not sure what you are doing with the tempArr but I will leave it in.

def is_bst_tree(treenode, temp_arr):
    if treenode.isempty():  # this should be a method on your treenode data type
        return True

    # do the check of the curent value 
    # based on being on the left or right 
    # side of tree   

    # return False # this should be done after you have made the relevant checks


    return is_bst_tree(treenode.right,temp_arr) and is_bst_tree(treenode.left, temp_arr)

The "bubbling up" will occur from the recursive calls at the end of the function based on the checks or the fact that you are at a leaf. You will be left with a chain of boolean and ... and boolean which will resolve to True or False.

You could adapt the algorithm from https://en.wikipedia.org/wiki/Binary_search_tree#Verification For the min and max values see Maximum and Minimum values for ints

Bubbling up return values from recursive call in Python

2 Answers2