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

Simply do the post order traversal and keep track of number of nodes in left and right subtree.At any node when its left and right are processed,then check if left+right+1(for parent node)=4,then it means one subtree with 4 nodes encountered.

T.c => O(n) ,postorder

Answer 2

int result;
count(node n)
{
   if ( !n ) return 0;

   if ( n->left ) 
   { no_of_nodes_in_left_subtree = 1 + count ( n->left ) }

   if ( n->right ) 
   { no_of_nodes_in_right_subtree = 1 + count ( n->right ) }

   if ( no_of_nodes_in_left_subtree + no_of_nodes_in_right_subtree == 4 ) 
   { result ++; }

   return ( no_of_nodes_in_left_subtree + no_of_nodes_in_right_subtree ) ;

}

Every node is traversed once. Hence O(1) and answer a = 1; b =0.

Answer 3

DFS can calculate the number of nodes in a subtree. Time Complexity = $O(n+m)^{[*]}$

So, $O(n)$.

Hence, $a=1, \ b=0$

 

Answer is 1

---

$^{[*]}$ n is the number of nodes, m is the number of edges.

Answer 4

just use the function of counting nodes in the subtree . everytime the nodes of a subtree are counted just check if it is equal to yur requirement . time complexity of counting all  node in O(n) so this is also O(n).

function;;

int number(struct node *qwerty)
{int e,f,w;

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

Comments

This is incorrect, as your code will not work correctly on Tree with just 4 nodes.