Dec 6th, 2013
18
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # Begin exam Code by Prof. Danny Heap
2. class BTNode:
3.     """Node in a binary tree"""
4.
5.     def __init__(self: 'BTNode', value: object, left: 'BTNode',
6.                  right: 'BTNode') -> None:
7.         """
8.        Create a new BTNode with value and (possibly)
9.        children left and right.
10.        """
11.         self.value, self.left, self.right = value, left, right
12.
13.
14. def count_nodes(n: BTNode) -> (int, int):
15.     """
16.    Return a tuple containing the number of interior nodes and the number
17.    of leaves in the tree rooted at n, or (0,0) if n is None.
18.
19.
20.    <Test cases go here>
21.    """
22.     # Begin student code
23.     if not n: return 0, 0 # this is a line of code[added when checking answers]
24.     if not n.left and not n.right:
25.         return 0, 1
26.     else:
27.         left_count = (0, 0)
28.         right_count = (0, 0)
29.
30.         if n.left:
31.             left_count = count_nodes(n.left)
32.             left_count[0] += 1
33.
34.         if n.right:
35.             right_count = count_nodes(n.right)
36.             right_count[0] += 1
37.
38.         return left_count[0] + right_count[0], left_count[1] + right_count[1]
RAW Paste Data