GATE 2014 CS (CS1) – Question 22
A rooted n-node binary tree is represented using pointers. The best upper bound for counting subtrees with exactly four nodes is $O(n^a\log^bn)$. Find a + 10b.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 1 to 1
Explanation
A postorder traversal computes each rooted subtree size as1+left_size+right_size. Increment a counter whenever that size equals4. Each node takes constant work, so time is O(n)=O(n¹log⁰n), giving **a+10b=1**. Recomputing sizes separately is unnecessary.