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 min{no. of leaf-nodes in
left-subtree of x, no. of leaf-nodes in right-subtree of x) then the worst-case time complexity of
the program is:​

Answer 1

Answer:

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. here g(x) is mentioned as a function which takes the time complexity which you answered as Θ(n) to calculate.. here we have n leave so, total log n levels.. so we get Θ(n log n).

Explanation: