in DS
449 views
5 votes
5 votes

A program takes as input a binary tree (not necessarily balanced) with $n$ nodes and computes for each node, the no. of leaf nodes in the sub-tree rooted at that node. The worst case time complexity of the program is

  1. $\Theta(n)$
  2. $\Theta(n \log n)$
  3. $\Theta\left(n^2 \right)$
  4. $\Theta\left(n^2 \log n \right)$
in DS
by
449 views

1 comment

plz explain someone
0
0

5 Answers

9 votes
9 votes
Best answer

We just have to do a tree traversal and for leaf nodes return 1 and for other nodes call the function recursively on the left and right nodes and return their sum. The following code would do

int fun (node * x)
{
    if(!x) return 0;
    if(x -> left == NULL && x-> right == NULL) return 1;
    return fun(x->left) + fun(x->right);
}

And tree traversal is $\Theta(n)$.

selected by
by

4 Comments

Yes, but the solution is also doing it rt? though it is not explicitly saving the value but just returning.
3
3
@Arjun your answer is the worst case of the most efficient algorithm, how about this, I start the tree traversal on every node of a  skewed binary tree then it is surely going to take theta(n2) time, since nothing is mentioned in the question about which algorithm to take (most efficient or least efficient ) then it should be n2.
0
0

Yes, Answer should be O(n).

Explanation:

Since left/right skewed tree are considered to be the worst case in binary trees.

Consider a left skewed tree/right skewed tree with n nodes.

For left skewed tree, according to the given equation above:

T(n) = T(n-1) + 1

Solving this, we get: T(n) = n+1 = O(n).

0
0
0 votes
0 votes

Wouldn't the answer be O(n2) for a left or right skewed binary tree?

1 comment

skew doesnt cause a problem here.
1
1
0 votes
0 votes
ans should be O(n^2)..if tree is right skewed or left skewed then no of comparisons will be (n+ n-1 + n-2 +.......1) which is O(n^2)

2 Comments

what is there to compare here? See the answer now.
0
0
edited by
@Arjun sir, it not say to find total no. of leaf nodes . It say, what are the no.of leaf nodes for EACH & EVERY NODES.

so it takes n*n=O(n^2) time.
1
1
0 votes
0 votes
it time complexity is O(n)

1 comment

Can you explain this
0
0
Answer:

Related questions