425 views
0 votes
0 votes

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: 

min(number of leaf-nodesin left-subtree of x,number of leaf-nodesin right-subtree of x)

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

THIS is gate2004-85.....what if for the same question it was  (min(number of nodesin left-subtree of x,number of nodesin right-subtree of x)

(i.e) it was number of nodes rather than leaf nodes

Please log in or register to answer this question.

Related questions

3 votes
3 votes
0 answers
1
srestha asked Mar 20, 2018
285 views
Let X and Y be normal distribution with mean $\alpha$ and $\beta$ respectively. If $Z=max(X,Y)$then the mean of Z is given by_______________
103 votes
103 votes
11 answers
2
0 votes
0 votes
0 answers
3
vg653 asked Dec 18, 2018
426 views
The Minimum number of possible edges in an undirected graph with n vertices and k components is ______
1 votes
1 votes
0 answers
4