Consider the following Python code: def count(child_dict, i): if i not in…
2024
Consider the following Python code:
def count(child_dict, i):
if i not in child_dict.keys():
return 1
ans = 1
for j in child_dict[i]:
ans += count(child_dict, j)
return ans
child_dict = dict()
child_dict[0] = [1,2]
child_dict[1] = [3,4,5]
child_dict[2] = [6,7,8]
print(count(child_dict,0))
Which ONE of the following is the output of this code?
- A.
6
- B.
1
- C.
8
- D.
9
Attempted by 73 students.
Show answer & explanation
Correct answer: D
Key idea: the function returns 1 for the current node plus the counts of all nodes in each child subtree.
Compute leaf nodes: nodes 3, 4, 5, 6, 7, 8 have no children, so count(...) = 1 for each.
Compute node 1: it has children 3, 4, 5, so count(1) = 1 (node 1) + 1 + 1 + 1 = 4.
Compute node 2: it has children 6, 7, 8, so count(2) = 1 (node 2) + 1 + 1 + 1 = 4.
Compute root 0: count(0) = 1 (root) + count(1) + count(2) = 1 + 4 + 4 = 9.
Therefore the code prints 9.