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

Answer: $1$..

Explanation:

1. Come to the $4^{\text{th}}$ level up from the leaf node of the given binary tree, which can be done using tree traversal in $O(n)$.
2. For each node present in the level check whether it's subtree having exactly $4$ nodes.. which can be  done in constant time for each node, since it's subtree having constant number of nodes..
3. nodes in the level is less than n.. so its complexity is $O(n)$

Therefore, $a = 1$ and $b = 0$

$a + 10b = 1$ Answer

Comments

traversal for DFS or BFS using adjacency list will always take O(V+E).

so, even for ‘m’ nodes we have total ‘n’ nodes in the tree, so number of edges = n-1.

So V+E=2n−1 ⇒ O(V+E) = O(2n−1) =  O(n) only.

---

i have one doubt,if we apply a=1,b=0

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

hoe it is calculated

---

its (log n)^0 . Read the ques carefully !!

Answer 2

We need to traverse all nodes at least once, and we need only one traversal. If $num(child1) + num (child2) + 1 = 4,$ then output yes.

So, $a$ must be $1$ and $b = 0\implies a + 10b = 1.$

Comments

Arjun sir here post order traversal will work?

---

@Shweta Nair 

it should be T(n)= T(n->left) + T(n->right) + C but here we cant predict left & right and also can't take  T(n/2) + T(n/2) so, instead of  using that approach we should think that,

we have to traverse O(n) node & for each node check for 4 children take O(1) time so it is O(1).

---

@talha hashim yes it is just variation of some line changes in the postorder traversal code

Answer 3

It is easier to look @ Program here, This program will take O(N) time, so Answer is 1.

int count = 0;

int number(struct node *Root)
{

int left , right , total;

    if(qwerty)
    {
        left =number(qwerty->left);   // number of node in left 
        right =number(qwerty->right);                   // number of node in right 
        if( (left  + right  + 1) == 4 )                                 check requirement
        {
            count++;
        }
        total =1 + left  + right  ;        
      return total ;
    }

Comments

value of count should be return here. why total?

[EDIT]: this doubt has been solved on fb group, and in future if one have same doubt then he can see this fb thread.

https://www.facebook.com/groups/core.cs/permalink/1323885154310401/

---

total is nothing but the number of nodes in the sub-tree, rooted at the current node.

Answer 4

we can perform a Depth First Search on the binary tree to get the answer.

for a graph the running time of DFS is O(V²) with adjency matrix.

But here we are dealing with a binary tree which is also a graph BUT it has a maximum of 2 adjacent nodes.

So our adjency matrix will be of size 2*V instead of V².

Hence we can have a more tighter upper bound here in case of binary trees which is O(V)

Hence the answer is 1 :)

Comments

Nice approach brother :)