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 145Assignment 8a8q1.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?
Advertisement
Answer
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)) )