455 views

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

### 1 comment

plz explain someone

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

by

Yes, but the solution is also doing it rt? though it is not explicitly saving the value but just returning.
@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.

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

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

by

### 1 comment

skew doesnt cause a problem here.
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)

what is there to compare here? See the answer now.
edited
@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.
it time complexity is O(n)

### 1 comment

Can you explain this

1 vote