GATE CSE 2014 Set 1 | Question: 12

Question

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.

Comments

what if it was binary search tree insteadof binary tree ? what would be the answer then?

---

easiest approach.

---

not just the easiest approach, its most logical and actual approach

Answer 1

There are just a constant number of 4-node rooted binary trees -- I count 14 in total (8 height-3 trees, 4 height-2 trees in which the root has 2 children, and 2 height-2 trees in which the root has 1 child). So even with the new, broader definition, it would be possible to check each node in the tree to see which of the 14 possible 4-node rooted binary trees are rooted at this node, and add this count to a grand total, all in O(n) time. thus a = 1 and b = 0 so ans will be 1.

 

source c - What is the best way to determine the number of subtrees having exactly 4 nodes? - Stack Overflow

Answer 2

I simply used the subtract and conquer method:

if any recurrence relation in the form of  ==== >»  T(n)=aT(n-b)+f

if f=O(n^k) where k>=0

Then T(n)=O(n^k)    if(a>1)

T(n)=O(n^(k+1))  if(a==1)

T(n)=O(n^k(a^(n/b))) if(a<1)

According to the problem :

The recurrence relation will be as

T(n)=T(n-4)+1

1===(O(n^0))

so, k=0;

applying the above theorem we get T(n)=O(n^(0+1))  => T(n)=O(n) =O(n^a(logn^b)

then a=1 and b=0

Then  a+10b=1.

The answer is 1.

Answer 3

Here we hav to traverse the whole tree to get the solution ... It can be preorder, inorder or postorder which will give O(n) ... so answer is 1 ...

Comments

int count ;

int CountNode(struct node *R){

     if(R == NULL) return 0;

      total = 1+CountNode(R->left) +CountNode(R->right);

      if(total == 4)

          count++;

      return total;

}