Midterm 2
Just yesterday we had our second midterm and this time I
feel much better about it. I thought that I simply would like to share my
solution here in case someone wants to compare the results or maybe point on
any mistakes that I have possible done. I hope I remembered the problems as they were.
Question 1 asked to count the number of internal nodes and the number of leaves.
def count_nodes(n: BTNode) -> (int, int):
if (n is None):
return (0, 0)
elif (n.left is None) and (n.right is None):
return (0, 1)
else:
interns = 1 + count_nodes(n.left)[0] + count_nodes(n.right)[0]
leaves = count_nodes(n.left)[1] + count_nodes(n.right)[1]
return (interns, leaves)
Question 2 asked to count the number of even integers in a binary tree.
def count_even(n: BTNode) -> int:
if (n is None):
return 0
if (n.value % 2 == 0):
return (1 + count_even(n.left) + count_even(n.right))
else:
return (count_even(n.left) + count_even(n.right))
Question 3 asked to construct a path to the min element in the BST and return the first LLNode in the chain (I hope it didn't ask to construct the shortest path).
def min_path(n: BSTNode) -> LLNode:
if (n is None):
return None
else:
llnode = LLNode(n.value, min_path(n.left))
return llnode
My code was similar, which is relieving to see! Like your solution to the third question, mine was pretty short too - which made me doubt my solution. I didn't want to risk writing this on a test and getting it wrong, but for Question 3, this one-liner is a valid solution, right?
ReplyDelete"return None if not n else LLNode(n.value, min_path(n.left))"
It's pretty funny how recursion can grant you 8 marks on a test with only a few lines! :)
Yes, I'm pretty sure that the one line solution is equivalent to the longer one.
ReplyDeleteOH,last question , i forgot the NONE case, so they took off my mark ,thank you for sharing your code, help me a lot.
ReplyDelete