edited by
24,273 views
90 votes
90 votes
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 __________.
edited by

11 Answers

Best answer
75 votes
75 votes

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

edited by
115 votes
115 votes
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.$
35 votes
35 votes

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 ;
    }

20 votes
20 votes

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(V2) 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 V2.

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

Hence the answer is 1 :)

Answer:

Related questions

100 votes
100 votes
10 answers
3