A program takes as input a balanced binary search tree with

Home » Programming & Data Structure » Programming and data structure miscellaneous » 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 (number of leaf-nodes in left – subtree of x,number of leaf – nodes in right – subtree of x) then the worst – case time complexity of the program is

1. Θ (n)
2. Θ (n log n)
3. Θ (n²)
4. Θ (n² log n)

Correct Option: B

At the root node (first level) the cost would be Θ (n/2) as the tree is balanced.
At next level, we have 2 nodes and for each of them cost of computing g(x) will be Θ (n / 4). So, total cost at second level = Θ (n / 2). Similarly at each level (total cost per level and not the cost per node in a level) the cost would be Θ (n / 2)and so for logn levels it would be Θ (n logn).