Using recursion to count nodes in a binary tree, test equality of linked lists, and find extrema of a linked list

Question

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 < maybe_min:
 least = ll.value
 if maybe_min != None and ll.value > maybe_min:
 least = maybe_min
 if maybe_max == None or ll.value >= maybe_max:
 most = ll.value
 if maybe_max != None and ll.value < maybe_max:
 most = maybe_max
 return least, most

• Jamal: Please quit starting titles with "clean code". The desire for clean code is already implied on this site, so it adds nothing.

Answer 1

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)

Answer 2

Python not my favorite language (but recursion is).

I would personally move the recursion out of the tests. Thus you do the test for return and other things first. Then the final statement is just a recursive call. This is because a lot work has gone into optimizing tail recursion and you can get significant benifits from it.

So:

def count(t,p):
 if t == None or t.value == None:
 return 0
 result = 1 if p(t.value) else 0
 return result + count(t.right, p) + count(t.left, p)

and

def equal(ll1,ll2):
 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 False
 return equal(ll1.next, ll2.next)

• LucyBen: @LokiAstari- Thanks. Any input on the min_max function?