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?
Answer: D. 9 — CONCEPTA recursive tree-counting function can return the size of the subtree rooted at the current node. The base case contributes one node, while a non-leaf…
- A.
6
- B.
1
- C.
8
- D.
9
Attempted by 115 students.
Show answer & explanation
Correct answer: D
CONCEPT
A recursive tree-counting function can return the size of the subtree rooted at the current node. The base case contributes one node, while a non-leaf contributes one for itself plus the counts returned by all child subtrees.
APPLICATION
Nodes 3, 4, 5, 6, 7, and 8 are absent from child_dict, so each corresponding call reaches the base case and returns 1.
For node 1, ans starts at 1 and adds the three leaf returns: count(child_dict, 1) = 1 + 1 + 1 + 1 = 4.
For node 2, the same structure gives count(child_dict, 2) = 1 + 1 + 1 + 1 = 4.
For node 0, ans starts at 1 and adds both child-subtree returns: count(child_dict, 0) = 1 + 4 + 4 = 9.
CROSS-CHECK
The represented tree contains the root 0, the internal nodes 1 and 2, and the six leaves 3–8: 1 + 2 + 6 = 9 nodes. This independently matches the recursive return value, so the code prints 9.