TypeError while executing Binary tree code

Question

I am getting an error while testing the following function. Can anybody help me with this?

code:

class treenode(object):

def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right
    
def largest_leaf_value(tnode):
    if tnode is None:
        return None
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    if lres > res:
        res = lres
    if rres > res:
        res = rres
    return res

Here's the test script:

# test tree with 1 level i.e. root value only
input_tree = T.treenode(1)
expected = 3

result = a8q1.largest_leaf_value(input_tree)
assert result is expected, "{}: copying empty tree returned unexpected result".format(test_item)

# test a longer tree
input_tree = T.treenode(1, T.treenode(2, T.treenode(3, T.treenode(4, T.treenode(5)))))
expected = 5

result = a8q1.largest_leaf_value(input_tree)
assert result is expected, "{}: copying empty tree returned unexpected result".format(test_item)

And here's the error I am getting:

Traceback (most recent call last):
  File "D:/CMPT 145/Assignment 8/a8q1_testing.py", line 60, in <module>
    result = a8q1.largest_leaf_value(input_tree)
  File "D:\CMPT 145\Assignment 8\a8q1.py", line 44, in largest_leaf_value
    if lres > res:
TypeError: '>' not supported between instances of 'NoneType' and 'int'

Please let me know why is this happening?

Answer 1

As your largest_leaf_value will return None in its recursion base case, you need to be ready for lres or rres to get None assigned to them.

The type error occurs on the lines where you compare lres or rres with res, and tells you that a None value cannot be compared with res.

So you have two possibilities: either avoid that comparison from executing when lres or rres is None, or, don't let your function return None, but instead return -infinity (since that value is smaller than all other finite numerical values).

Solution with the first approach:

def largest_leaf_value(tnode):
    if tnode is None:
        return None
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    # Only compare when not None:
    if lres is not None and lres > res:
        res = lres
    if rres is not None and rres > res:
        res = rres
    return res

Solution with the second approach:

def largest_leaf_value(tnode):
    if tnode is None:
        # Don't return None, but -infinity
        return float("-inf")
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    if lres > res:
        res = lres
    if rres > res:
        res = rres
    return res

Note that this will behave differently when you pass an empty tree (i.e. None) as argument in the initial call. Mathematically it is not defined what the maximum is in an empty collection, so it will depend on what you expect to happen in that case.

Finally, you can use max() to make the second version a bit shorter:

def largest_leaf_value(tnode):
    return (float("-inf") if tnode is None else
        max(tnode.data, largest_leaf_value(tnode.left), largest_leaf_value(tnode.right))
    )