Using recursion to count nodes in a binary tree, test equality of linked lists, and find extrema of a linked list I am working with a some small functions to test recursion. I am fairly new to Python and am wondering if there is a cleaner way to get the job done.

def count(t,p):

    ''' recursive function when passed a binary tree (it doesn’t matter if it is a 
    binary search tree) and a predicate as arguments; it returns a count of all the 
    values in the tree for which the predicate returns True. '''
    if t == None or t.value == None:
        return 0
    elif p(t.value):
        return 1 + count(t.right, p) + count(t.left, p)
    else:
        return count(t.right, p) + count(t.left, p)



def equal(ll1,ll2):

    ''' recursive function when passed two linked lists; it returns whether or not 
    the linked lists contain exactly the same values in the same order. '''
    if ll1 == None and ll2 == None:
        return True
    if (ll1 != None and ll2 == None) or\
        (ll2 != None and ll1 == None):
        return False
    elif ll1.value == ll2.value:
        return equal(ll1.next, ll2.next)
    else:
        return False


def min_max(ll):

    ''' a recursive when passed a linked list; it returns a 2-tuple containing the 
    minimum value followed by the maximum value. If the linked list is empty, return 
    (None, None) '''
    if ll == None:
        return None, None
    maybe_min, maybe_max  = min_max(ll.next)
    if maybe_min == None or ll.value &lt; maybe_min:
        least = ll.value
    if maybe_min != None and ll.value &gt; maybe_min:
        least = maybe_min
    if maybe_max == None or ll.value &gt;= maybe_max:
        most = ll.value
    if maybe_max != None and ll.value &lt; maybe_max:
        most = maybe_max
    return least, most
It is better to test for x is None rather than x == None.



Avoid using single-letter variable names — they may make sense to you, but not to anyone else.

I don't see any reason why a node should be automatically not counted if its value is None.  Shouldn't it be up to the predicate to decide whether nodes with None as a value are counted or not?

You can eliminate a case by taking advantage of the fact that int(False) is 0 and int(True) is 1.

def count(tree_node, predicate):
    """Counts the tree_node and its descendants whose value satisfies the predicate."""
    if tree_node is None:
        return 0
    else:
        return int(predicate(tree_node.value)) + \
               count(tree_node.left, predicate) + \
               count(tree_node.right, predicate)




Stylistically, it would be better to consistently use either one long if… elif chain or just ifs with early returns.  I also suggest putting the recursive case at the end of the function.

(ll1 != None and ll2 == None) or (ll2 != None and ll1 == None) can be simplified.

def equal(ll1, ll2):
    """Recursively checks whether two linked lists contain the same values
    in the same order."""
    if ll1 is None and ll2 is None:
        return True
    if ll1 is None or ll2 is None:
        return False
    if ll1.value != ll2.value:
        return False
    return equal(ll1.next, ll2.next)




Assuming that the linked list contains no None data values, the logic can be simplified.

def min_max(ll):
    """Returns a 2-tuple of the minimum and maximum values.
    If ll is empty, returns (None, None)."""
    if ll is None:
        return None, None
    if ll.next is None:
        return ll.value, ll.value
    least, greatest = min_max(ll.next)
    return min(ll.value, least), max(ll.value, greatest)