Dark Mode

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

- $\Theta(n)$
- $\Theta(n \log n)$
- $\Theta\left(n^2 \right)$
- $\Theta\left(n^2 \log n \right)$

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

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

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