A program takes as input a balanced binary search tree with n leaf nodes and…

PYQ GATE 2004

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

  1. A.

    Θ(n)

  2. B.

    Θ(nLogn)

  3. C.

    Θ(n2)

  4. D.

    Θ(n2log n)

Attempted by 508 students.

Sign up free to check your answer

Sign up free

Explore the full course: Data Structures

Loading lesson…