The Gateway to Computer Science Excellence
+55 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 __________.
in DS by Veteran (106k points)
edited by | 6.8k views
Can someone give structure of this Tree?

9 Answers

+46 votes
Best answer

Answer: $1$..


  1. Come to the 4th 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

by Active (5k points)
edited by
how preorder traversal wil tell number of childrens to particular node while traversing?

please explian?
tree traversal only will use to reach at 4th level from leaf ,from that brute force will use which will take constant time

Given, the tree is represented using pointers. So, adjacency list representation is fine for this tree.

Now using DFS, the number of subtrees with exactly four nodes can be done in O(V+E) time.

Since E=V-1 so time complexity is O(V).


How a=1 could u explain?
@Rprabhakar1 in question it is mention O(n^a log^bn) but after putting the value a=1 and b=0, we are getting time complexity is O(n),

@Ayush Upadhyaya

Yup. A simple graph traversal using BFS or DFS will solve this problem. Either of them (BFS or DFS) has the time complexity of $\mathrm{O}(V+E)$.

Here $V=n$. As it's the tree, $E=n-1$.

So $V+E=2n-1\Rightarrow \mathrm{O}(V+E)=\mathrm{O}(2n-1)=\mathrm{O}(n)$.

From leaf to come to 4th level you will need back pointers right? Are we to assume tree representation is done by double pointers?
+57 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.$
by Veteran (432k points)
I calculated it using this recurrence relation,

      T(n) = T(n/2) + T(n/2) + c

T(n/2) - each for left subtree as well as right subtree.

Solving this, T(n)= O(n)

Is this the right way to approach the problem.

@Shweta Nair

We dont know whether tree is balanced,in case it is balanced then your recurence is correct. If it is left skew or right skew then it is not

@rahul sharma 5  Thanks for correcting. I missed out on that. So when we consider left or right skewed tree, the recurrence relation should be T(n) = T(n-1)+c right? Even then after solving we get T(n) = O(n).

So considering both cases, the best upper bound i.e tightest upper bound will be O(n).
Yes ,correct. We need to traverse each node exactly one time.So,thehta(n)
Ya consider the worst case scenario ..
Arjun sir here post order traversal will work?


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

+24 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;

        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
        total =1 + left  + right  ;        
      return total ;

by Boss (41.9k points)

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.

total is nothing but the number of nodes in the sub-tree, rooted at the current node.
+17 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 :)

by Active (4k points)
Nice approach brother :)
+5 votes
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.

by Junior (943 points)
+4 votes
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
by Boss (25.6k points)
0 votes

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.

by Loyal (7k points)
–1 vote

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


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

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

by Boss (16.1k points)
This is incorrect, as your code will not work correctly on Tree with just 4 nodes.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,395 answers
105,446 users