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?
Answer
(D)
Explanation
child_dict describes a tree: node 0 has children 1 and 2, node 1 has children 3, 4, 5, and node 2 has children 6, 7, 8. A node that is not a key (3 to 8) is a leaf and returns 1. Any other node returns 1 for itself plus the counts of its children, so count counts every node in the subtree.
count(child_dict, 1)\(= 1 + 3 = 4\), and likewisecount(child_dict, 2)\(= 4\).count(child_dict, 0)\(= 1 + 4 + 4 = 9\).
The tree has the nine nodes 0 to 8. Option A (6) counts only the leaves, and option C (8) leaves out the root.
Answer: D