Question 1 (5 marks) Python

evaluation of Boolean expressions: if a is false in the expression “a and b”, then b is never eval￾uated. Similarly, if a is true in the expression “a or b”, then b is never evaluated. Python’s equivalent

of Java’s null pointer is None; it can be used to indicate the absence of a value. In the following piece

of code, the implementation of add_positive exploits short-circuit evaluation to ensure we never ask

whether None is greater than 0, a comparison that would raise an exception:

class Adder:

sum = 0

def add_positive(self, x):

if x is not None and x > 0:

self.sum += x

xs = [1, -1, None, 0, None, 3, -2, 4, None]

sum = Adder()

for x in xs:

sum.add_positive(x)

print(sum.sum)

Now suppose Python did not use short circuit evaluation, that is, it always evaluates both operands

of “and” or “or”. How would you implement add_positive so it behaves exactly the same as the

implementation provided here? Provide your Python code of add_positive.

Question 2 (10 marks) Here is a bit of Python code that uses recursion to traverse a binary tree:

class Node:

def new(rep):

if type(rep) is list:

left = Node.new(rep[0])

right = Node.new(rep[1])

return Internal(left, right)

else:

return Leaf(rep)

class Leaf(Node):

def __init__(self, val):

self.val = val

def sum_leaves(self, sum):

return sum + self.val

class Internal(Node):

def __init__(self, left, right):

self.left = left

self.right = right

def sum_leaves(self, sum):

return self.right.sum_leaves(self.left.sum_leaves(sum))

class Tree:

# Build a tree from a list representation. This performs no error

# checking. We simply assume that the list representation represents

# a proper binary tree.

def __init__(self, rep):

self.root = Node.new(rep)

# Traverse the tree and return the sum of all leaves

def sum_leaves(self):

return self.root.sum_leaves(0)

treerep = [[3, [5, -1]], [[1, 7], [2, [3, [11, -9]]]]]

tree = Tree(treerep)

print(tree.sum_leaves())

The procedure sums the values stored at the tree’s leaves. Now assume that you do not want to use re￾cursion for some reason. Provide the Python code of an iterative implementation of the Tree.sum_leaves

function. You are allowed to use any data structure you like, but your code must ensure that the num￾ber of stack frames on the call stack is bounded by a constant at all times, no matter how big the tree is.