+40 votes
4k views
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 __________.
asked in DS
edited | 4k views
0
Can someone give structure of this Tree?

## 8 Answers

+33 votes
Best answer

Answer: $1$..

Explanation:

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

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

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

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

0
How a=1 could u explain?
+38 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.$
answered by Veteran (359k points)
0
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.
0

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

+2
@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).
0
Yes ,correct. We need to traverse each node exactly one time.So,thehta(n)
0
Ya consider the worst case scenario ..
0
Arjun sir here post order traversal will work?
+18 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 ;
}

answered by Boss (43k points)
+4

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/

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

answered by Active (3.9k points)
+1
Nice approach brother :)
+3 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.

answered by Junior (847 points)
+3 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
answered by Boss (25.1k 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).

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

answered by Boss (16k points)
0
This is incorrect, as your code will not work correctly on Tree with just 4 nodes.
–1 vote
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 ...
answered by Boss (11.4k points)
Answer:

+20 votes
3 answers
1
+20 votes
4 answers
2
+43 votes
5 answers
3