GATE CS 2014 Set 1 Q12 — Trees

To find the number of subtrees having exactly $4$ nodes in a rooted binary tree of $n$ nodes, we can use a bottom-up (post-order) traversal approach.

For any node $u$ in the binary tree, the size of the subtree rooted at $u$, denoted by $S(u)$, is given by:

where the size of a non-existent child (null pointer) is $0$.

Algorithm:

1. Perform a post-order traversal of the tree.
2. For each node, compute its subtree size in $O(1)$ time using the sizes of its left and right children (which are already computed due to the post-order nature of the traversal).
3. Maintain a global counter. If $S(u) = 4$, increment the counter.

Complexity Analysis:

• Since each node is visited exactly once and we perform a constant number of operations at each node, the total time complexity is $\Theta(n)$.
• Thus, the best upper bound on the time required is $O(n)$.

We are given that the upper bound is $O(n^a \log^b n)$. Comparing this with $O(n^1 \log^0 n)$:

We need to find the value of $a + 10b$: