GATE CSE 2004 | Question: 85

Question

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is: $$\Large \min \left ( \substack{\text{number of leaf-nodes}\\\text{in left-subtree of $x$}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of $x$}}\right )$$

Then the worst-case time complexity of the program is?

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

Comments

The correct answer is B. $\Theta(n \log n)$.

To ensure the complexity is $\Theta(n \log n)$ rather than just bounded by $O(n \log n)$, we can evaluate a perfectly balanced binary search tree.

In a perfectly balanced tree with $n$ leaf nodes:

• At the root level (Level 0): There is $1$ node. Its left and right subtrees each have $n/2$ leaves. Cost = $1 \times \min(n/2, n/2) = n/2$.

• At Level 1: There are $2$ nodes. Each has left and right subtrees with $n/4$ leaves. Cost = $2 \times \min(n/4, n/4) = n/2$.

• At Level $i$: There are $2^i$ nodes. Each has left and right subtrees with $n/2^{i+1}$ leaves. Cost = $2^i \times (n/2^{i+1}) = n/2$.

The tree has a total of $\log_2(n)$ levels of internal nodes. Summing the cost across all levels:

$$\text{Total Cost} = \sum_{i=0}^{\log_2(n)-1} \frac{n}{2} = \frac{n}{2} \log_2(n)$$

Because the cost is exactly proportional to $n \log n$ in the typical balanced case, the worst-case time complexity is firmly $\Theta(n \log n)$.

---

nice one

---

https://www.youtube.com/live/cL_46jo2Us0?si=d3UhpC5ZIRQwVVI8&t=2267

Answer 1

B. At the root node (first level) the cost would be $\Theta\left(\frac{n}{2}\right)$ as the tree is balanced.

At next level, we have 2 nodes and for each of them cost of computing $g(x)$ will be $\Theta\left(\frac{n}{4}\right)$. So, total cost at second level $= \Theta\left(\frac{n}{2}\right).$ Similarly at each level (total cost per level and not the cost per node in a level) the cost would be $\Theta\left(\frac{n}{2}\right)$ and so for $\log n$ levels it would be $\Theta({n} \log n).$

PS: Even if we change $\min$ to $\max$ in the defintion of $g(x)$ we get the same answer.

Comments

@tusharp Bhaiya, where are we calculating the complexity of g(x) here?We are just summing up the cost of every node in the level and multiplying with logn.How will this give the complexity of g(x)?

---

@Tejaswee_Bommaluleni

imagine a perfect binary tree :

$no. \ of \ nodes = \log_{2}15 = 4 \approx log_{2}n$

$level \ 0: \ $$no.\ of \ leaf \ nodes \ for \ root \ node = n/2 = 8$

$level \ 1: \ $$no.\ of \ leaf \ nodes \ for \ a \ node \ in \ level \ 1 = n/4 \ (leaf \ nodes: \ 7,8,9,10 \ or \ 11,12,13,14) = 4$

$since \ 2 \ nodes \ in \ level \ 1, \ n/4 + n/4 \ [n/4 \ is \ cost \ of \ a \ node] = n/2 \ (cost \ of \ level)$

$similarly \ in \ level \ 2 \ (n/8 + n/8 + n/8 + n/8) \ [n/8 \ is \ cost \ per \ node]$
$= \ n/2 \ (cost \ of \ level) \ for \ nodes \ of \ level \ 2$

$Total \ cost = \ cost \ per \ level \ * \ no.\ of \ levels = n/2 * logn = O(nlogn)$
 

---

@coderatul we are calculating gx which depends of leaf nodes count,
counting the leafs , leaf count take dfs meaning O(n), and we should move forward from there .

at each node leaf count = O(n).

so at root = O(n/2) +O(n/2) == n
at level 1 > O(n/4) +O(n/4) +O(n/4) + O(n/4) == n
.
.
........ at each level == n 

so total cost = N * total levels
= N*logN

Am I right?

Answer 2

Do a post order traversal and store and return $\min \left( \text{g}(x \rightarrow left), \text{g}(x \rightarrow right ) \right )$ for all non leaf nodes and store $0$ for all leaf nodes and return 1. BST being balanced, with n leaf nodes we can have total 2n nodes and complexity of tree traversal is linear in number of nodes- $\Theta(n)$.

But this is just computing the time complexity of $g(x)$ for each node- not exactly what is asked in question.

Actually the procedure I gave is computing the COST of computing the value of $g(x)$ which would have been correct had the question been defined as 

$g(x) = \Large \min \left ( \substack{\text{number of leaf-nodes}\\ \text{in left-subtree of x}}\;,\; \substack{\text{number of leaf-nodes}\\\text{in right-subtree of x}}\right )$. 

The correct answer for this would be $\Theta(n \log n)$ as at each level, the cost is $\Theta(n)$ and we have $\log n$ levels since the tree is balanced.  

Correct Answer: $B$

Comments

Sir, if we are taking cost of every level as n then that means we are only considering cost of visiting leaf nodes because n is no of leaf nodes. Shouldn't we also consider internal nodes that we will be visiting.

---

If we apply DP then it will be O(n) ??

 

---

@Akash Kanase Bhaiya,where are we calculating the complexity of g(x) here?We are just summing up the cost of every node in the level and multiplying with logn.How will this give the complexity of g(x)?

Answer 3

1.if we use simple divide and conquer technique(without using extra space)

we first need to count no. of leaf in left subtree,then no. of leaf in right subtree+compare them to find minimum.

T(n)=2T(n/2)+1----->O(n)

but we need to compute this for every node.

so, cost at 0 th level=O(n)

cost at 1st level=n/2+n/2=O(n)

cost at 2nd level=n/4+n/4+n/4+n/4=O(n)\

we have total of logn levels (because tree is balanced) and cost at every level is O(n).

Hence total cost is=n*logn=O(nlogn)

2.if we use extra memory to store no of leaf at left subtree and at right subtree for every node

we don't need to go to last level for every node.

1.compute for every leaf node.

2.then use those values to compute at all nodes at (h-1) level till root.

so, time complexity of this method is equal to O(n),since we are calculating value for each node and doing only one comparison. 

space complexity is also O(n),since we are using extra memory for every node.

since question is asking about worst case time complexity,so we have O(nlogn) .

Comments

@jatin is it always true while calculating worst case , we choose algo with less space complexity O(1) in above case ?

Answer 4

Let us assume a balanced binary tree containing n leaf nodes. We have to compute g(x) corresponding to every node x and the cost of computing g(x) is 

min(number of leaf-nodes in left-subtree of x,number of leaf-nodes in right-subtree of x).

we start from root and compute g(x) corresponding to every node.g(root) = min(n/2 , n/2) = Θ(n/2) =Θ(n).

Cost at level 1 :Θ(n).

Cost corresponding to second level :

g(left_node)= min(n/4,n/4)=n/4

g(right_node)=min(n/4,n/4)=n/4

Total cost at level 2 :Θ(n/4 + n/4) =Θ(n/2)=Θ(n)

Similarly total cost at level 3 : Θ(n/8 + n/8 +n/8 + n/8)=Θ(n/2)=Θ(n)

...There are totally log n levels since it is a balanced binary search tree and cost at every level is Θ(n).

There fore time complexity  of the program is Θ(n) . log n =Θ(n logn).

Comments

we have total of logn levels (because tree is balanced) and cost at every level is O(n).

Hence total cost is= n*logn =O(nlogn)

---

thank you sir . analysed my mistake and got your point.

---

@ balaeinstein  

Edit your answer, please . Put correct result.

---

ok sir

Answer 5

The actual question which is asked is different than what we people understood

Comments

Great job on the solution; it’s spot on!👏

Answer 6

Height of balanced binary search tree = logn

So there are logn levels in tree

At one node we need to find left and right sub tree leaves

The recurrence relation will be T(n) = left sub tree + right sub tree + root

T(n) = T(n/2)+T(n/2)+1 = 2T(n/2) + 1 = O(n)

There are logn levels so T(n) = O(nlogn)

Comments

nice