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
