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?
6
1
8
9
ANSWER
The program prints 9, which is option (D).
Official answer: DSource: Official answer key, GATE 2024 DA (IISc Bengaluru)
The dictionary stores a tree as child lists: key 0 has children 1 and 2, key 1 has children 3, 4, 5, and key 2 has children 6, 7, 8. Keys 3 to 8 are not in the dictionary, so they are leaves.
count(child_dict, i) returns 1 at once when i is not a key. Otherwise it starts with ans = 1 (the node itself) and adds count(child_dict, j) for every child j. So it returns the number of nodes in the subtree rooted at i.
For each leaf 3, 4, 5, 6, 7, 8, the test i not in child_dict.keys() is true, so count returns 1.
count(child_dict, 1): ans = 1, then ans += 1 three times (children 3, 4, 5), so it returns .
count(child_dict, 2): ans = 1, then ans += 1 three times (children 6, 7, 8), so it returns .
count(child_dict, 0): ans = 1, then ans += count(child_dict, 1) gives , then ans += count(child_dict, 2) gives . The function returns 9, and print shows 9. This equals the number of nodes, 0 to 8, in the tree. The answer is option (D).
KEY IDEA
The recursion counts the nodes of a tree stored as a dictionary of child lists. Each call returns 1 for itself plus the counts of its children, and a key missing from the dictionary is a leaf that returns 1. The output is 1 + (1 + 3) + (1 + 3) = 9.
WATCH OUT FOR
Counting only the keys of the dictionary (3) or only the leaves (6), or forgetting that a missing key still returns 1 and so counts as a node. Another slip is returning 0 for leaves, which would give 3 instead of 9.
From the GATE 2024 DA paper. Every question of this paper · Download the full paper · All 10 Python questions, with notes
