GATE Overflow | Data Structures | Test 1 | Question: 16

Question

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

• A. $\Theta(n)$
• B. $\Theta(n \log n)$
• C. $\Theta\left(n^2 \right)$
• D. $\Theta\left(n^2 \log n \right)$

Comments

plz explain someone

Answer 1

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

Comments

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

Answer 2

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

Comments

skew doesnt cause a problem here.

Answer 3

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)

Comments

what is there to compare here? See the answer now.

---

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

Answer 4

it time complexity is O(n)

Comments

Can you explain this

Answer 5

What would be the answer if, we are asked to compute number of nodes in the subtree rooted at each node of the binary tree?