ISRO CS 2023 Q.3: solution and answer

Official answer: A or BSource: ISRO's revised and final answer key of 16 February 2024

1. The diameter of a binary tree is the number of nodes (or edges) on the longest path between any two nodes. That path need not pass through the root.

2. For each node $v$, the longest path whose topmost node is $v$ has $h(\text{left})+h(\text{right})+1$ nodes. The diameter is the maximum of this value over all nodes.

3. The naive method computes the heights of both subtrees separately at every node. Each height computation costs $O(n)$, so the total is $O(n^2)$ in the worst case, for example a skewed tree.

4. The better method does one post-order traversal. Each call returns the height of its subtree and updates a running maximum diameter using the children's heights. A node's height follows from its children's heights in $O(1)$.

5. Every node is visited once and does $O(1)$ work, so $T(n)=T(k)+T(n-k-1)+O(1)$, which solves to $T(n)=O(n)$.

6. A lower bound of $\Omega (n)$ also holds, because any node could lie on the longest path, so every node must be examined. Hence the tight bound is $\Theta (n)$, which is option (b).

7. Option (a), $O(n^2)$, is the cost of the naive method and is also a valid upper bound, since $O(n)\subseteq O(n^2)$, but it is not tight. Options (c) and (d) are impossible, because even reading all the nodes takes $\Omega (n)$.