The GATE Grind

GATE 2024 DA – Question 38

Programming, Data Structures and Algorithms · Programming in Python · 2 marks · Multiple choice

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?

  1. 6
  2. 1
  3. 8
  4. 9

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) 9

Explanation

The function counts the nodes of the tree rooted at $i$. The tree has the root 0, its children 1 and 2, and the children 3, 4, 5 of node 1 and 6, 7, 8 of node 2. The nodes 3 to 8 are leaves (they return 1). So $count(1) = 1 + 3 = 4$, $count(2) = 4$ and $count(0) = 1 + 4 + 4 = 9$.