1,072 views
6 votes
6 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)$

5 Answers

Best answer
10 votes
10 votes

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
0 votes
0 votes

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

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

Related questions

0 votes
0 votes
1 answer
2
Arjun asked Oct 10, 2016
281 views
Consider the array given below:20 10 9 8 7 6 5It isa full binary tree in array representationa complete binary tree in array representationa max-heap in array representat...
1 votes
1 votes
2 answers
3
Arjun asked Oct 10, 2016
764 views
With 5 distinct nodes, the maximum no. of binary trees that can be formed is _____