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

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

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

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

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?
0
@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),
+3

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

0
From leaf to come to 4th level you will need back pointers right? Are we to assume tree representation is done by double pointers?
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)
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.
+1

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

+4
@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?
0

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

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

by Boss (41.9k 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.

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

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)
+1
Nice approach brother :)
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)
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)

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

So, $O(n)$.

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

$^{[*]}$ 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).

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

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